In distributed systems, atomic broadcast or total order broadcast is a broadcast messaging protocol that ensures that messages are received reliably and in the same order by all participants (Défago et al.. 2004). This must be considered against FIFO broadcast and Causal broadcast to understand the differences.
This problem is usually considered in environments where participants can fail, for example, by crashing. Participants that never fail are called correct, the others are faulty. The following properties are usually required from an atomic broadcast protocol.
- If a correct participant broadcasts a message, then all correct participants will eventually receive it.
- Uniform agreement
- If a participant delivers a message, then all correct participants will eventually deliver it as well.
- Uniform integrity
- Any given message is delivered by each participant at most once, and only if it was previously broadcast.
- Uniform total order
- If some participant delivers message A after message B, then every participant delivers A only after it has delivered B.
The definitions for validity and integrity may be sometimes formulated in different way. E.g. Michel Raynal et al. define atomic broadcast as having following properties:
- If participant delivers a message, it was broadcast by some participant.
- Any given message is delivered by each participant at most once.
- If correct process (process which is permanently up) broadcast message, all correct processes eventually delivers message OR if a participant delivers a message, then all correct participants will eventually deliver it as well.
- Total order
- essentially the same as in previous definition.
Schiper et al. defines validity property of atomic broadcast differently:
- if correct process broadcasts m, then it delivers m
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 (Défago et al.. 2004). One widely popular technology in which atomic broadcast is available as a primitive is virtual synchrony, a kind of computing 'model' used for fault tolerance and data replication in many real-world systems and products.
- Défago, X., Schiper, A., and Urbán, P. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36, 4 (Dec. 2004), 372-421. DOI=10.1145/1041680.1041682 (alternate source)
- Rodrigues L, Raynal M.: Atomic Broadcast in Asynchronous Crash-Recovery Distributed Systems , ICDCS '00: Proceedings of The 20th International Conference on Distributed Computing Systems ( ICDCS 2000)
- Ekwall, R.; Schiper, A.: Solving Atomic Broadcast with Indirect Consensus. Dependable Systems and Networks, 2006. DSN 2006. International Conference on 2006.