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. January, 2000.
Previous version in the fifteenth ACM Symposium on Principles of
Distributed Computing (PODC) May 1996, pages 68-76.
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.
Download book chapter:
ps,
pdf,
ps.gz.
Israel mirror site:
ps.gz.
Download PODC paper:
ps,
ps.gz.
Israel mirror site:
ps.gz.
Last modified: Mon Jul 1 14:33:49 EDT 2002