Browse Prior Art Database

Asynchronous Atomic Broadcast

IP.com Disclosure Number: IPCOM000119592D
Original Publication Date: 1991-Feb-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 75K

Publishing Venue

IBM

Related People

Cristian, F: AUTHOR

Abstract

This article describes a protocol for atomically broadcasting messages in networks of processes connected by a communication network characterized by unbounded message delays. The protocol is useful in maintaining the consistency of replicated data at these processes. Also described are two optimizations of the protocol that achieve weaker data consistency but require less message overhead and increase availability of updates to the replicated data.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Asynchronous Atomic Broadcast

      This article describes a protocol for atomically
broadcasting messages in networks of processes connected by a
communication network characterized by unbounded message delays.  The
protocol is useful in maintaining the consistency of replicated data
at these processes.  Also described are two optimizations of the
protocol that achieve weaker data consistency but require less
message overhead and increase availability of updates to the
replicated data.

      The protocol consists of two parts: the membership protocol and
the train protocol.  The membership protocol achieves agreement on
the identity of the processes that form a group in the presence of
process failures and process joins.  The train protocol totally
orders all updates applied to the replicated data by group members.

      Membership computation is a three-phase protocol which is
initiated either by a process which starts a join or by a process
which detects a failure.  That process sends messages to all other
processes asking them to form a new group.  Every process that
receives such a message responds with an acknowledgement.  The
initiator collects the identity of all responding processes and then
sends to all of them the membership of the new group, computed as
being the set of all alive processes that have responded to the
invitation.  Agreement on membership is ensured by the fact that all
members accept the membership computed centrally by the initiator.
Because of communication partitions which can result from unbounded
message delays or too many failures, it is possible that several
groups exist at the same time.  To ensure that only one group can
update the replicated data, only the majority group (which contains a
majority of all processes) can execute the train protocol.

      Once a majority group is formed, the initiator begins a "train"
through the group in a cyclic order containing ea...