Lower Bounds for Randomized Consensus under a Weak Adversary

Lower Bounds for Randomized Consensus under a Weak Adversary

This paper studies the inherent trade-off between termination probability and total step complexity of randomized consensus algorithms. It shows that for every integer $k$, the probability that an $f$-resilient randomized consensus algorithm of $n$ processes does not terminate with agreement within...

Full description

Bibliographic Details
Main Authors: Attiya, Hagit, Censor-Hillel, Keren
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Society for Industrial and Applied Mathematics 2011
Online Access:http://hdl.handle.net/1721.1/64943

Similar Items

Similar Items