{{Short description|Distributed computing primitive}} In fault-tolerant distributed computing, an '''atomic broadcast''' or '''total order broadcast''' is a broadcast where all correct processes in a system of multiple processes receive the same set of messages in the same order; that is, the same sequence of messages.<ref name="Kshemkalyani"/><ref name="Defago2004"/> The broadcast is termed "atomic" because it either eventually completes correctly at all participants, or all participants abort without side effects. Atomic broadcasts are an important distributed computing primitive.
== Properties == The following properties are usually required from an atomic broadcast protocol: # Validity: if a correct participant broadcasts a message, then all correct participants will eventually receive it. # Uniform Agreement: if one correct participant receives a message, then all correct participants will eventually receive that message. # Uniform Integrity: a message is received by each participant at most once, and only if it was previously broadcast. # Uniform Total Order: the messages are totally ordered in the mathematical sense; that is, if any correct participant receives message 1 first and message 2 second, then every other correct participant must receive message 1 before message 2.
Rodrigues and Raynal<ref name="RR"/> and Schiper et al.<ref name=Schiper/> define the integrity and validity properties of atomic broadcast slightly differently.
Note that total order is not equivalent to FIFO order, which requires that if a process sent message 1 before it sent message 2, then all participants must receive message 1 before receiving message 2. It is also not equivalent to "causal order", where if message 2 "depends on" or "occurs after" message 1 then all participants must receive message 2 after receiving message 1. While a strong and useful condition, total order requires only that all participants receive the messages in the same order, but does not place other constraints on that order such as that in which the messages are sent.<ref name="Dermot Kelly"/>
== Fault tolerance == Designing an algorithm for atomic broadcasts is relatively easy if it can be assumed that computers will not fail. For example, if there are no failures, atomic broadcast can be achieved simply by having all participants communicate with one "leader" which determines the order of the messages, with the other participants following the leader.
However, real computers are faulty; they fail and recover from failure at unpredictable, possibly inopportune, times. For example, in the follow-the-leader algorithm, what if the leader fails at the wrong time? In such an environment achieving atomic broadcasts is difficult.<ref name="Kshemkalyani"/> A number of protocols have been proposed for performing atomic broadcast, under various assumptions about the network, failure models, availability of hardware support for multicast, and so forth.<ref name=Defago2004/>
== Equivalent to consensus == In order for the conditions for atomic broadcast to be satisfied, the participants must effectively "agree" on the order of receipt of the messages. Participants recovering from failure, after the other participants have "agreed" on an order and started to receive the messages, must be able to learn and comply with the agreed order. Such considerations indicate that in systems with crash failures, atomic broadcast and consensus are equivalent problems.<ref name="Chandra-Toueg"/>
A value can be proposed by a process for consensus by atomically broadcasting it, and a process can decide a value by selecting the value of the first message which it atomically receives. Thus, consensus can be reduced to atomic broadcast.
Conversely, a group of participants can atomically broadcast messages by achieving consensus regarding the first message to be received, followed by achieving consensus on the next message, and so forth until all the messages have been received. Thus, atomic broadcast reduces to consensus. This was demonstrated more formally and in greater detail by Xavier Défago, et al.<ref name=Defago2004/>
A fundamental result in distributed computing is that achieving consensus in asynchronous systems in which even one crash failure can occur is impossible in the most general case. This was shown in 1985 by Michael J. Fischer, Nancy Lynch, and Mike Paterson, and is sometimes called the FLP result.<ref name="FLP"/> Since consensus and atomic broadcast are equivalent, FLP applies also to atomic broadcast.<ref name="Dermot Kelly"/> The FLP result does not prohibit the implementation of atomic broadcast in practice, but it does require making less stringent assumptions than FLP in some respect, such as about processor and communication timings.
== Algorithms == The Chandra-Toueg algorithm<ref name="Chandra-Toueg"/> is a consensus-based solution to atomic broadcast. Another solution has been put forward by Rodrigues and Raynal.<ref name="RR"/>
The Zookeeper Atomic Broadcast (ZAB) protocol is the basic building block for Apache ZooKeeper, a fault-tolerant distributed coordination service which underpins Hadoop and many other important distributed systems.<ref name="Zab"/><ref name="Medeiros"/>
Ken Birman has proposed the virtual synchrony execution model for distributed systems, the idea of which is that all processes observe the same events in the same order. A total ordering of the messages being received, as in atomic broadcast, is one (though not the only) method for attaining virtually synchronous message receipt.
== References == <references> <ref name="Kshemkalyani">{{Cite book|title = Distributed Computing: Principles, Algorithms, and Systems|url = https://www.cs.uic.edu/~ajayk/DCS-Book|url-access = limited|last1 = Kshemkalyani|first1 = Ajay|publisher = Cambridge University Press|year = 2008|isbn = 9781139470315|pages = 583–585|last2 = Singhal|first2 = Mukesh}}</ref> <ref name="Defago2004">{{cite journal|doi=10.1145/1041680.1041682|title=Total order broadcast and multicast algorithms|year=2004|last1=Défago|first1=Xavier|last2=Schiper|first2=André|last3=Urbán|first3=Péter|journal=ACM Computing Surveys|volume=36|issue=4|pages=372–421|s2cid=207155989 |url=https://infoscience.epfl.ch/record/52563/files/IC_TECH_REPORT_200356.pdf}}</ref> <ref name="FLP">{{cite journal|url=https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf|author=Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson|title=Impossibility of Distributed Consensus with One Faulty Process|journal=Journal of the ACM|volume=32|issue=2|pages=374–382|doi=10.1145/3149.214121|year=1985|s2cid=207660233 }}</ref> <ref name="Dermot Kelly">{{cite web|url=http://www.cs.nuim.ie/~dkelly/CS402-06/Group%20Communication.htm|author=Dermot Kelly|title=Group Communication}}</ref> <ref name="RR">Rodrigues L, Raynal M.: Atomic Broadcast in Asynchronous Crash-Recovery Distributed Systems [https://doi.org/10.1109/ICDCS.2000.840941], ICDCS '00: Proceedings of the 20th International Conference on Distributed Computing Systems ( ICDCS 2000)</ref> <ref name="Schiper">{{cite book|doi=10.1109/dsn.2006.65|isbn=0-7695-2607-1|chapter=Solving Atomic Broadcast with Indirect Consensus|title=International Conference on Dependable Systems and Networks (DSN'06)|year=2006|last1=Ekwall|first1=R.|last2=Schiper|first2=A.|pages=156–165|s2cid=14315628 |url=https://infoscience.epfl.ch/record/83547/files/TechReport_LSR_2006_01.pdf}}</ref> <ref name="Chandra-Toueg">{{cite journal|doi=10.1145/226643.226647|title=Unreliable failure detectors for reliable distributed systems|year=1996|last1=Chandra|first1=Tushar Deepak|last2=Toueg|first2=Sam|journal=Journal of the ACM|volume=43|issue=2|pages=225–267|s2cid=9835158 |doi-access=free|hdl=1813/7192|hdl-access=free}}</ref> <ref name="Medeiros">{{cite web|url=http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf|website=Helsinki University of Technology - Laboratory of Theoretical Computer Science|title=ZooKeeper's atomic broadcast protocol: Theory and practice|date=March 20, 2012|author=André Medeiros}}</ref> <ref name="Zab">{{cite book|author=Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini, Yahoo! Research|title=2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN)|s2cid=206611670|chapter=Zab: High-performance broadcast for primary-backup systems|year=2011|pages=245–256|doi=10.1109/DSN.2011.5958223|isbn=978-1-4244-9233-6}}</ref> </references>
{{DEFAULTSORT:Atomic Broadcast}} Category:Distributed computing problems