Most distributed systems require coordination between all components involved. With the steady growth of such systems, the probability of failures increases, which necessitates fault-tolerant agreement protocols. The most common practical agreement protocol, for such scenarios, is leader-based atomic broadcast. In this work, we propose AllConcur, a distributed system that provides agreement through a leaderless concurrent atomic broadcast algorithm, thus, not suffering from the bottleneck of a central coordinator. In AllConcur, all components exchange messages concurrently through a logical overlay network that employs early termination to minimize the agreement latency. Our implementation of AllConcur supports standard sockets-based TCP as well as high-performance InfiniBand Verbs communications. AllConcur can handle up to 135 million requests per second and achieves 17x higher throughput than today's standard leader-based protocols, such as Libpaxos. Therefore, AllConcur not only offers significant improvements over existing solutions, but enables novel hitherto unattainable system designs in a variety of fields.
Many existing algorithms and systems can be used to implement atomic broadcast; we discuss here only the most relevant subset. D 'e fago, Schiper, and Urb ' a n provide a general overview of atomic broadcast algorithms @cite_26 . They define a classification based on how total order is established: by the sender, by a sequencer or by the destinations @cite_23 . uses destinations agreement to achieve total order, i.e., agreement on a message set. Yet, unlike other destinations agreement algorithms, is entirely decentralized and requires no leader.
@cite_26 @cite_23
2130264930 2133943294
Total order broadcast and multicast (also called atomic broadcast multicast) present an important problem in distributed systems, especially with respect to fault-tolerance. In short, the primitive ensures that messages sent to a set of processes are, in turn, delivered by all those processes in the same total order. We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and which ones require a majority of correct processes. We prove that Consensus and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus, the above results also apply to Atomic Broadcast. A companion paper shows that one of the failure detectors introduced here is the weakest failure detector for solving Consensus [ 1992].