LIPIcs.OPODIS.2016.27.pdf
- Filesize: 404 kB
- 14 pages
Document
m-Consensus Objects Are Pretty Powerful
Author
-
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
Ammar Qadri. m-Consensus Objects Are Pretty Powerful. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.27
Abstract
A recent paper by Afek, Ellen, and Gafni introduced a family of deterministic objects O_{m,k}, for m,k >= 2, with consensus numbers m such that, for each k >= 2, O_{m,k} is computationally less powerful than O_{m,k+1} in systems with at least mk+m+k processes. This paper gives a wait-free implementation of O_{m,k} from (m + 1)-consensus objects and registers in systems with any finite number of processes. In order to do so, it introduces a new family of objects which helps us to understand the power of m-consensus among more than m processes.
Subject Classification
Keywords
- Deterministic Consensus Hierarchy
- Wait-free Implementation
- Tournament
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
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), pages 97-106, 2016.
-
Yehuda Afek, Eli Gafni, and Adam Morrison. Common2 extended to stacks and unbounded concurrency. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pages 218-227, 2006.
-
Yehuda Afek, Eli Gafni, John Tromp, and Paul M. B. Vitányi. Wait-free test-and-set (extended abstract). In Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG), pages 85-94, 1992.
-
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), pages 159-170, 1993.
-
Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, 1991.
-
Ophir Rachman. Anomalies in the wait-free hierarchy. In Proceedings of the 8th International Workshop on Distributed Algorithms (WDAG), pages 156-163, 1994.