Atomic broadcast
Encyclopedia
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.
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. 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.
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.
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. 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
Virtual synchrony
Virtual synchrony is an interprocess messaging passing technology. Virtual synchrony systems allow programs running in a network to organize themselves into process groups, and to send messages to groups...
, a kind of computing 'model' used for fault tolerance and data replication in many real-world systems and products.