Atomic broadcast

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 problem is usually considered in environments where participants can fail, for example, by crashing. Participants who never fail are called correct, the others are faulty. 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 deliver 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 B only after it has delivered A.

The definitions for validity and integrity may be sometimes formulated in different way. E.g. Michel Raynal et al.^[1] define atomic broadcast as having following properties:

Validity

If participant delivers a message, it was broadcast by some participant.

Integrity

Any given message is delivered by each participant at most once.

Termination

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.^[2] defines validity property of atomic broadcast differently:

Validity

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.

References

• 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)