A Simple Proof of the Uniform Consensus Synchronous Lower Bound.

Authors: Idit Keidar and Sergio Rajsbaum.

In Information Processing Letters (IPL) 85(1), pages 47-52, January 2003.

Abstract:

We give a simple and intuitive proof of a f+2 round lower bound for uniform consensus. That is, we show that for every uniform consensus algorithm tolerating t failures, and for every f < t-1, there is an execution with f failures that requires f+2 rounds.

Download:

Preprint of IPL paper: ps, ps.gz, pdf.
Talk slides (powerpoint): pps, pps.gz.

Last modified: Sun Dec 29 13:15:07 IST 2002