Atomic broadcast

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Validity
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.[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[edit]

  1. ^ Rodrigues L, Raynal M.: Atomic Broadcast in Asynchronous Crash-Recovery Distributed Systems [1], ICDCS '00: Proceedings of The 20th International Conference on Distributed Computing Systems ( ICDCS 2000)
  2. ^ Ekwall, R.; Schiper, A.: Solving Atomic Broadcast with Indirect Consensus. Dependable Systems and Networks, 2006. DSN 2006. International Conference on 2006.