LIPIcs.DISC.2020.54.pdf
- Filesize: 324 kB
- 3 pages
Document
Brief Announcement: On Decidability of 2-Process Affine Models
Authors
-
Part of:
Volume:
34th International Symposium on Distributed Computing (DISC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-10-07
Cite AsGet BibTex
Petr Kuznetsov and Thibault Rieutord. Brief Announcement: On Decidability of 2-Process Affine Models. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 54:1-54:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.54
https://doi.org/10.4230/LIPIcs.DISC.2020.54
Abstract
Affine models of computation, defined as subsets of iterated immediate-snapshot runs, capture a wide variety of shared-memory systems: wait-freedom, t-resilience, k-concurrency, and fair shared-memory adversaries. The question of whether a given task is solvable in a given affine model is, in general, undecidable.
In this paper, we focus on affine models defined for a system of two processes. We show that task computability of 2-process affine models is decidable and presents a complete hierarchy of five equivalence classes of 2-process affine models.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
Keywords
- Affine tasks
- Decidability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Elizabeth Borowsky and Eli Gafni. A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In PODC, pages 189-198, 1997.
-
Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-write memory and k-set consensus as an affine task. In OPODIS, pages 6:1-6:17, 2016.
-
Eli Gafni and Elias Koutsoupias. Three-processor tasks are undecidable. SIAM J. Comput., 28(3):970-983, 1999.
-
Eli Gafni, Petr Kuznetsov, and Ciprian Manolescu. A generalized asynchronous computability theorem. In PODC, pages 222-231, 2014.
-
Maurice Herlihy and Sergio Rajsbaum. The decidability of distributed decision tasks (extended abstract). In STOC, pages 589-598, 1997.
- Petr Kuznetsov and Thibault Rieutord. On decidability of 2-process affine models, 2020. URL: http://arxiv.org/abs/2008.02099.
-
Petr Kuznetsov, Thibault Rieutord, and Yuan He. An asynchronous computability theorem for fair adversaries. In PODC, pages 387-396, 2018.
-
Vikram Saraph, Maurice Herlihy, and Eli Gafni. Asynchronous computability theorems for t-resilient systems. In DISC, pages 428-441, 2016.