LIPIcs.OPODIS.2016.5.pdf
- Filesize: 0.54 MB
- 16 pages
Document
Bounded Disagreement
Authors
-
Part of:
Volume:
20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-04-06
Cite As Get BibTex
David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. Bounded Disagreement. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.5
Abstract
A well-known generalization of the consensus problem, namely, set agreement (SA), limits the number of distinct decision values that processes decide. In some settings, it may be more important to limit the number of "disagreers". Thus, we introduce another natural generalization of the consensus problem, namely, bounded disagreement (BD), which limits the number of processes that decide differently from the plurality. More precisely, in a system with n processes, the (n, l)-BD task has the following requirement: there is a value v such that at most l processes (the disagreers) decide a value other than v. Despite their apparent similarities, the results described below show that bounded disagreement, consensus, and set agreement are in fact fundamentally different problems. We investigate the relationship between bounded disagreement, consensus, and set agreement. In particular, we determine the consensus number for every instance of the BD task. We also determine values of n, l, m, and k such that the (n, l)-BD task can solve the (m, k)-SA task (where m processes can decide at most k distinct values). Using our results and a previously known impossibility result for set agreement, we prove that for all n >= 2, there is a BD task (and a corresponding BD object) that has consensus number n but can not be solved using n-consensus and registers. Prior to our paper, the only objects known to have this unusual characteristic for n >= 2 (which shows that the consensus number of an object is not sufficient to fully capture its power) were artificial objects crafted solely for the purpose of exhibiting this behaviour.
Subject Classification
Keywords
- Consensus
- Set Agreement
- Asynchronous System
- Distributed Algorithms
- Shared Memory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873-890, Sep 1993. URL: http://dx.doi.org/10.1145/153724.153741.
- Yehuda Afek, Faith Ellen, and Eli Gafni. Deterministic objects: Life beyond consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC'16, pages 97-106, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933057.2933116.
- Yehuda Afek, Eli Gafni, and Adam Morrison. Common2 extended to stacks and unbounded concurrency. Distributed Computing, 20(4):239-252, 2007. URL: http://dx.doi.org/10.1007/s00446-007-0023-3.
- Yehuda Afek, Adam Morrison, and Guy Wertheim. From bounded to unbounded concurrency objects and back. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, pages 119-128, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993806.1993823.
- Yehuda Afek, Eytan Weisberger, and Hanan Weisman. A completeness theorem for a class of synchronization objects. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, PODC'93, pages 159-170, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/164051.164071.
- Armando Castañeda, Damien Imbs, Sergio Rajsbaum, and Michel Raynal. Renaming is weaker than set agreement but for perfect renaming: A map of sub-consensus tasks. In Proceedings of the 10th Latin American International Conference on Theoretical Informatics, LATIN'12, pages 145-156, Berlin, Heidelberg, 2012. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-29344-3_13.
- Soma Chaudhuri. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, PODC'90, pages 311-324, New York, NY, USA, 1990. ACM. URL: http://dx.doi.org/10.1145/93385.93431.
- Soma Chaudhuri and Paul Reiners. Understanding the set consensus partial order using the borowsky-gafni simulation (extended abstract). In Proceedings of the 10th International Workshop on Distributed Algorithms, WDAG'96, pages 362-379, London, UK, UK, 1996. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=645953.675630.
- Matei David. A single-enqueuer wait-free queue implementation. In Rachid Guerraoui, editor, Distributed Computing, volume 3274 of Lecture Notes in Computer Science, pages 132-143. Springer Berlin Heidelberg, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30186-8_10.
- Matei David, Alex Brodsky, and Faith Ellen Fich. Restricted stack implementations. In Proceedings of the 19th International Conference on Distributed Computing, DISC'05, pages 137-151, Berlin, Heidelberg, 2005. Springer-Verlag. URL: http://dx.doi.org/10.1007/11561927_12.
- David Eisenstat. Two-enqueuer queue in common2. CoRR, abs/0805.0444, 2008. URL: http://arxiv.org/abs/0805.0444.
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, Apr 1985. URL: http://dx.doi.org/10.1145/3149.214121.
- Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy. Subconsensus tasks: Renaming is weaker than set agreement. In Shlomi Dolev, editor, Distributed Computing, volume 4167 of Lecture Notes in Computer Science, pages 329-338. Springer Berlin Heidelberg, 2006. URL: http://dx.doi.org/10.1007/11864219_23.
- Eli Gafni, Michel Raynal, and Corentin Travers. Test&set, adaptive renaming and set agreement: a guided visit to asynchronous computability. In Reliable Distributed Systems, 2007. SRDS 2007. 26th IEEE International Symposium on, pages 93-102, Oct 2007. URL: http://dx.doi.org/10.1109/SRDS.2007.8.
- Maurice Herlihy. Impossibility results for asynchronous pram (extended abstract). In Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'91, pages 327-336, New York, NY, USA, 1991. ACM. URL: http://dx.doi.org/10.1145/113379.113409.
- Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 11(1):124-149, Jan 1991. URL: http://dx.doi.org/10.1145/114005.102808.
- Maurice Herlihy and Sergio Rajsbaum. Set consensus using arbitrary objects (preliminary version). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC'94, pages 324-333, New York, NY, USA, 1994. ACM. URL: http://dx.doi.org/10.1145/197917.198119.
- Ophir Rachman. Anomalies in the wait-free hierarchy. In Proceedings of the 8th International Workshop on Distributed Algorithms, WDAG'94, pages 156-163, London, UK, UK, 1994. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=645951.675479.
- Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449-1483, Mar 2000. URL: http://dx.doi.org/10.1137/S0097539796307698.