Implementação e Avaliação do Protocolo de Difusão Atômica Rápida a Despeito de Colisões

Abstract

State Machine Replication, is a common technique for achieving fault tolerance that can be implemented by Atomic Broadcast primitives. Atomic Broadcast is usually implemented by solving infinitely many instances of the well-known consensus problem. This approach has the disadvantage of forcing the concurrent broadcast of messages that have not yet been decided, causing them to be re-proposed in new instances, therefore delaying execution. Collision-fast algorithms, which deliver many messages within two message steps in good runs, exist, but either make assumptions that may be too restrictive; require a certain degree of clock synchronization among nodes; do not deal efficiently with failures or have not been experimentally evaluated. In this work we propose an architecture to implement the Collision-fast Atomic Broadcast algoritm as part of a distributed service, exploring the parallelism in today’s machines, and also evaluating the performance of this protocol in a variety of scenarios, comparing it with other two protocols (Paxos and Multi-Ring Paxos). Moreover, this work aims at improving the protocol to allow speculative execution of delivered commands and make it resilient to Byzantine failures. Finally, we conjecture the impossibility of Byzantine failure tolerant Collision-fast protocols.