LIPIcs.OPODIS.2015.32.pdf
- Filesize: 435 kB
- 16 pages
Document
Generic Proofs of Consensus Numbers for Abstract Data Types
Authors
-
Part of:
Volume:
19th International Conference on Principles of Distributed Systems (OPODIS 2015)
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: 2016-10-13
Cite As Get BibTex
Edward Talmage and Jennifer Welch. Generic Proofs of Consensus Numbers for Abstract Data Types. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.OPODIS.2015.32
Abstract
The power of shared data types to solve consensus in asynchronous wait-free systems is a fundamental question in distributed computing, but is largely considered only for specific data types. We consider general classes of abstract shared data types, and classify types of operations on those data types by the knowledge about past operations that processes can extract from the state of the shared object. We prove upper and lower bounds on the number of processes which can use data types in these classes to solve consensus. Our results generalize the consensus numbers known for a wide variety of specific shared data types, such as compare-and-swap, augmented queues and stacks, registers, and cyclic queues. Further, since the classification is based directly on the semantics of operations, one can use the bounds we present to determine the consensus number of a new data type from its specification. We show that, using sets of operations which can detect the first change to the shared object state, or even one at a fixed distance from the beginning of the execution, any number of processes can solve consensus. However, if instead of one of the first changes, operations can only detect one of the most recent changes, then fewer processes can solve consensus. In general, if each operation can either change shared state or read it, but not both, then the number of processes which can solve consensus is limited by the number of consecutive recent operations which can be viewed by a single operation. Allowing operations that both change and read the shared state can allow consensus algorithms with more processes, but if the operations can only see one change a fixed number of operations in the past, we upper bound the number of processes which can solve consensus with a small constant.
Subject Classification
Keywords
- Distributed Data Structures
- Abstract Data Types
- Consensus Numbers
- Distributed Computing
- Crash Failures
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Paul C. Attie. Wait-free byzantine consensus. Inf. Process. Lett., 83(4):221-227, 2002. URL: http://dx.doi.org/10.1016/S0020-0190(01)00334-9.
- Rida A. Bazzi, Gil Neiger, and Gary L. Peterson. On the use of registers in achieving wait-free consensus. Distributed Computing, 10(3):117-127, 1997. URL: http://dx.doi.org/10.1007/s004460050029.
- Elizabeth Borowsky, Eli Gafni, and Yehuda Afek. Consensus power makes (some) sense! (extended abstract). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC'94, pages 363-372, New York, NY, USA, 1994. ACM. URL: http://dx.doi.org/10.1145/197917.198126.
- Wei Chen, Guangda Hu, and Jialin Zhang. On the power of breakable objects. Theor. Comput. Sci., 503:89-108, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.05.036.
- Sagar Chordia, Sriram K. Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani. Asynchronous resilient linearizability. In Yehuda Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 164-178. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41527-2_12.
- Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, 1985. URL: http://dx.doi.org/10.1145/3149.214121.
- Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, 1991. URL: http://dx.doi.org/10.1145/114005.102808.
- Prasad Jayanti and Sam Toueg. Some results on the impossibility, universality, and decidability of consensus. In Adrian Segall and Shmuel Zaks, editors, Distributed Algorithms, 6th International Workshop, WDAG'92, Haifa, Israel, November 2-4, 1992, Proceedings, volume 647 of Lecture Notes in Computer Science, pages 69-84. Springer, 1992. URL: http://dx.doi.org/10.1007/3-540-56188-9_5.
- Wai-Kau Lo and Vassos Hadzilacos. All of us are smarter than any of us: Nondeterministic wait-free hierarchies are not robust. SIAM J. Comput., 30(3):689-728, 2000. URL: http://dx.doi.org/10.1137/S0097539798335766.
- Ophir Rachman. Anomalies in the wait-free hierarchy. In Gerard Tel and Paul M. B. Vitányi, editors, Distributed Algorithms, 8th International Workshop, WDAG'94, Terschelling, The Netherlands, September 29 - October 1, 1994, Proceedings, volume 857 of Lecture Notes in Computer Science, pages 156-163. Springer, 1994. URL: http://dx.doi.org/10.1007/BFb0020431.
- Eric Ruppert. Consensus numbers of multi-objects. In Brian A. Coan and Yehuda Afek, editors, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC'98, Puerto Vallarta, Mexico, June 28 - July 2, 1998, pages 211-217. ACM, 1998. URL: http://dx.doi.org/10.1145/277697.277736.
- Eric Ruppert. Determining consensus numbers. SIAM J. Comput., 30(4):1156-1168, 2000. URL: http://dx.doi.org/10.1137/S0097539797329439.