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 |
| _version_ | 1826195526854377472 |
|---|---|
| author | Attiya, Hagit Censor-Hillel, Keren |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Attiya, Hagit Censor-Hillel, Keren |
| author_sort | Attiya, Hagit |
| collection | MIT |
| description | 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 $k(n-f)$ steps is at least $\frac{1}{c^k}$, for some constant $c$. A corresponding result is proved for Monte-Carlo algorithms that may terminate in disagreement. The lower bound holds for asynchronous systems, where processes communicate either by message passing or through shared memory, under a very weak adversary that determines the schedule in advance, without observing the algorithm's actions. This complements algorithms of Kapron et al. [Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2008, pp. 1038–1047] for message-passing systems, and of Aumann [Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1997, pp. 209–218] and Aumann and Bender [Distrib. Comput., 17 (2005), pp. 191–207] for shared-memory systems. |
| first_indexed | 2024-09-23T10:14:08Z |
| format | Article |
| id | mit-1721.1/64943 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:14:08Z |
| publishDate | 2011 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/649432022-09-30T19:47:47Z Lower Bounds for Randomized Consensus under a Weak Adversary Attiya, Hagit Censor-Hillel, Keren Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Censor-Hillel, Keren Censor-Hillel, Keren 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 $k(n-f)$ steps is at least $\frac{1}{c^k}$, for some constant $c$. A corresponding result is proved for Monte-Carlo algorithms that may terminate in disagreement. The lower bound holds for asynchronous systems, where processes communicate either by message passing or through shared memory, under a very weak adversary that determines the schedule in advance, without observing the algorithm's actions. This complements algorithms of Kapron et al. [Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2008, pp. 1038–1047] for message-passing systems, and of Aumann [Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1997, pp. 209–218] and Aumann and Bender [Distrib. Comput., 17 (2005), pp. 191–207] for shared-memory systems. Israel Science Foundation (grant 953/06) Simons Foundation (Postdoctoral Fellows Program) Israel Academy of Sciences and Humanities (Adams Fellowship Program) 2011-07-20T20:35:39Z 2011-07-20T20:35:39Z 2010-12 2009-03 Article http://purl.org/eprint/type/JournalArticle 1095-7111 0097-5397 http://hdl.handle.net/1721.1/64943 Attiya, Hagit, and Keren Censor-Hillel. “Lower Bounds for Randomized Consensus Under a Weak Adversary.” SIAM Journal on Computing 39.8 (2010) : 3885. © 2010 Society for Industrial and Applied Mathematics. en_US http://dx.doi.org/10.1137/090751906 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Attiya, Hagit Censor-Hillel, Keren Lower Bounds for Randomized Consensus under a Weak Adversary |
| title | Lower Bounds for Randomized Consensus under a Weak Adversary |
| title_full | Lower Bounds for Randomized Consensus under a Weak Adversary |
| title_fullStr | Lower Bounds for Randomized Consensus under a Weak Adversary |
| title_full_unstemmed | Lower Bounds for Randomized Consensus under a Weak Adversary |
| title_short | Lower Bounds for Randomized Consensus under a Weak Adversary |
| title_sort | lower bounds for randomized consensus under a weak adversary |
| url | http://hdl.handle.net/1721.1/64943 |
| work_keys_str_mv | AT attiyahagit lowerboundsforrandomizedconsensusunderaweakadversary AT censorhillelkeren lowerboundsforrandomizedconsensusunderaweakadversary |