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.


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