Early-Delivery Dynamic Atomic Broadcast.

Authors: Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch.

Extended abstract to appear in the 16th International Symposium on DIStributed Computing (DISC) October 2002, Toulouse, France.

Full version: Technical Report LCS-TR-840 Massachusetts Institute of Technology, Laboratory for Computer, April 2002.

Abstract:

We consider a problem of atomic broadcast in a dynamic setting where processes may join, leave voluntarily, or fail (by stopping) during the course of computation. We provide a formal definition of the Dynamic Atomic Broadcast problem and present and analyze a new algorithm for its solution in a variant of a synchronous model, where processes have approximately synchronized clocks.

Our algorithm exhibits constant message delivery latency in the absence of failures, even during periods when participants join or leave. To the best of our knowledge, this is the first algorithm for totally ordered multicast in a dynamic setting to achieve constant latency bounds in the presence of joins and leaves. When failures occur, the latency bound is linear in the number of actual failures.

Our algorithm uses a solution to a variation on the standard distributed consensus problem, in which participants do not know a priori who the other participants are. We define the new problem, which we call Consensus with Unknown Participants, and give an early-deciding algorithm to solve it.

Download:

DISC 2002 extended abstract: ps, ps.gz, pdf.
Full paper (MIT technical report): ps, ps.gz, pdf.


Last modified: Thu Jul 11 11:31:43 EDT 2002