LIPIcs.OPODIS.2019.16.pdf
- Filesize: 0.83 MB
- 15 pages
Document
On Deterministic Linearizable Set Agreement Objects
Authors
-
Part of:
Volume:
23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
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: 2020-02-11
Cite As Get BibTex
Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg. On Deterministic Linearizable Set Agreement Objects. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.16
Abstract
A recent work showed that, for all n and k, there is a linearizable (n,k)-set agreement object O_L that is equivalent to the (n,k)-set agreement task [David Yu Cheng Chan et al., 2017]: given O_L, it is possible to solve the (n,k)-set agreement task, and given any algorithm that solves the (n,k)-set agreement task (and registers), it is possible to implement O_L. This linearizable object O_L, however, is not deterministic. It turns out that there is also a deterministic (n,k)-set agreement object O_D that is equivalent to the (n,k)-set agreement task, but this deterministic object O_D is not linearizable. This raises the question whether there exists a deterministic and linearizable (n,k)-set agreement object that is equivalent to the (n,k)-set agreement task. Here we show that in general the answer is no: specifically, we prove that for all n ≥ 4, every deterministic linearizable (n,2)-set agreement object is strictly stronger than the (n,2)-set agreement task. We prove this by showing that, for all n ≥ 4, every deterministic and linearizable (n,2)-set agreement object (together with registers) can be used to solve 2-consensus, whereas it is known that the (n,2)-set agreement task cannot do so. For a natural subset of (n,2)-set agreement objects, we prove that this result holds even for n = 3.
Subject Classification
ACM Subject Classification
- Theory of computation → Concurrency
- Theory of computation → Parallel computing models
- Theory of computation → Distributed computing models
Keywords
- Asynchronous shared-memory systems
- consensus
- set agreement
- deterministic objects
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Elizabeth Borowsky and Eli Gafni. The implication of the Borowsky-Gafni simulation on the set-consensus hierarchy. CSD (Series). UCLA Computer Science Department, 1993. URL: https://books.google.ca/books?id=gpNeGwAACAAJ.
- 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: https://doi.org/10.1145/197917.198126.
- Armando Castañeda, Michel Raynal, and Sergio Rajsbaum. Specifying Concurrent Problems: Beyond Linearizability. CoRR, abs/1507.00073, 2015. URL: http://arxiv.org/abs/1507.00073.
- David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects. In Andréa W. Richa, editor, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.12.
- Soma Chaudhuri. More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Inf. Comput., 105(1):132-158, July 1993. URL: https://doi.org/10.1006/inco.1993.1043.
- 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.
- Maurice Herlihy and Nir Shavit. The Topological Structure of Asynchronous Computability. J. ACM, 46(6):858-923, November 1999. URL: https://doi.org/10.1145/331524.331529.
- Maurice Herlihy and Jeannette Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, July 1990. URL: https://doi.org/10.1145/78969.78972.
- Gil Neiger. Set-Linearizability. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '94, pages 396-, New York, NY, USA, 1994. ACM. URL: https://doi.org/10.1145/197917.198176.
- Michael Saks and Fotios Zaharoglou. Wait-free K-set Agreement is Impossible: The Topology of Public Knowledge. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 101-110, New York, NY, USA, 1993. ACM. URL: https://doi.org/10.1145/167088.167122.