Efficient Message Ordering in Dynamic Networks.

Authors: Idit Keidar and Danny Dolev.

In the fifteenth ACM Symposium on Principles of Distributed Computing (PODC) May 1996, pages 68-76.

Revised version appears as Chapter 3 of Dependable Network Computing, D. Avresky Editor, Kluwer Academic Publications. January, 2000.


We present an algorithm for totally ordering messages in the face of network partitions and site failures. The algorithm always allows a majority of connected processors in the network to make progress (i.e. to order messages), if they remain connected for sufficiently long, regardless of past failures. Furthermore, our algorithm always allows processors to initiate messages, even when they are not members of a connected majority component in the network. 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 two communication rounds, if no failures occur during these rounds.

Download PODC paper: ps, ps.gz. Israel mirror site: ps.gz.
Download book chapter: ps, pdf, ps.gz. Israel mirror site: ps.gz.

Previous version available as Keidar's masters thesis, the Hebrew University of Jerusalem, 1994, and also Technical Report CS95-5, Institute of Computer Science, The Hebrew University of Jerusalem: ps, ps.gz, abstract. Israel mirror site: ps, ps.gz.

Last modified: Mon Jul 1 14:35:11 EDT 2002