Title :
Collision-Fast Atomic Broadcast
Author :
Schmidt, R. ; Camargos, Lasaro ; Pedone, Fernando
Author_Institution :
Facebook, USA
Abstract :
Atomic Broadcast, an important abstraction in dependable distributed computing, is usually implemented by solving infinitely many instances of the well-known consensus problem. Some asynchronous consensus algorithms achieve the optimal latency of two (message) steps but cannot guarantee this latency even in good runs, those with timely message delivery and no crashes. This is due to collisions, a result of concurrent proposals. Collision-fast consensus algorithms, which decide within two steps in good runs, exist under certain conditions. Their direct application to solving atomic broadcast, though, does not guarantee delivery in two steps for all messages unless a single failure is tolerated. We show a simple way to build a fault-tolerant collision-fast Atomic Broadcast algorithm based on a variation of the consensus problem we call M-Consensus. Our solution to M-Consensus extends the Paxos protocol to allow multiple processes, instead of the single leader, to have their proposals learned in two steps.
Keywords :
broadcasting; distributed processing; fault tolerant computing; finite state machines; protocols; M-Consensus; Paxos protocol; asynchronous consensus algorithms; collision-fast consensus algorithms; consensus problem variation; dependable distributed computing; fault-tolerant collision-fast atomic broadcast algorithm; Computer crashes; Educational institutions; Electronic mail; Fault tolerance; Proposals; Protocols; Upper bound; Atomic Broadcas; Collision-fast Atomic Broadcast; Consensus; M-Consensus;
Conference_Titel :
Advanced Information Networking and Applications (AINA), 2014 IEEE 28th International Conference on
Conference_Location :
Victoria, BC
Print_ISBN :
978-1-4799-3629-8
DOI :
10.1109/AINA.2014.129