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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/64943 |