Totally Ordered Broadcast in the Face of Network
Partitions.
Exploiting Group Communication for Replication in
Partitionable Networks.
Authors:
Idit Keidar and
Danny Dolev.
Chapter 3 of Dependable Network Computing, D. Avresky Editor,
Kluwer Academic Publications. To appear.
Abstract:
This chapter presents an algorithm for Totally Ordered Broadcast in the
face of network partitions and process failures, using an underlying
group communication service as a building block. The algorithm always
allows a majority (or quorum) of connected processes in the network to
make progress (i.e., to order messages), if they remain connected for
sufficiently long, regardless of past failures. Furthermore, the
algorithm always allows processes to initiate messages, even when they
are not members of a majority component in the network. These messages
are disseminated to other processes using a gossip mechanism. Thus,
messages can eventually become totally ordered even if their initiator
is never a member of a majority component. The algorithm guarantees
that when a majority is connected, each message is ordered within at
most two communication rounds, if no failures occur during these
rounds.
Postscript Version:
ps,
ps.gz.
MIT mirror site:
ps,
ps.gz.
idish@theory.lcs.mit.edu
Last modified: Tue Sep 21 10:48:43 EDT 1999