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).
Abstract:
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.
Download:
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: Tue Jun 11 16:54:13 EDT 2002