On the Cost of Fault-Tolerant Consensus
When There Are No Faults - A Tutorial.

Authors: Idit Keidar and Sergio Rajsbaum.

Technical Report MIT-LCS-TR-821 MIT Laboratory for Computer Science, May 24, 2001.
Preliminary version in SIGACT News 32(2), Distributed Computing column, pages 45-63, June 2001 (published May 15th, 2001).


We consider the consensus problem in asynchronous models enriched with unreliable failure detectors or partial synchrony, where processes can crash or links may fail by losing messages. We study the number of communication steps performed by deterministic consensus algorithms for these models in failure-free executions. We show a tight lower bound of two communication steps. In the process of showing this bound, we give a simple unified proof of a number of different impossibility and lower bound results. Thus, we shed light on the relationship among different lower bounds, and at the same time, illustrate a general technique for obtaining simple and elegant lower bound and impossibility proofs. We illustrate the matching upper bound by describing previously published algorithms that achieve the lower bound.


Technical report MIT-LCS-TR-821, May 24, 2001: ps, ps.gz, pdf.
PODC 2002 Tutorial Slides (ppt), ppt.gz.

You can also download the SIGACT news column with a preliminary version of the paper, which has been superseded by the above technical report: ps, ps.gz, pdf.

Last modified: Fri Sep 12 08:47:35 IDT 2003