TY - GEN
T1 - Brief announcement
T2 - 34th International Symposium on Distributed Computing, DISC 2020
AU - Kuznetsov, Petr
AU - Rieutord, Thibault
N1 - Publisher Copyright:
© Petr Kuznetsov and Thibault Rieutord; licensed under Creative Commons License CC-BY 34th International Symposium on Distributed Computing (DISC 2020).
PY - 2020/10/1
Y1 - 2020/10/1
N2 - 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.
AB - 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.
KW - Affine tasks
KW - Decidability
U2 - 10.4230/LIPIcs.DISC.2020.54
DO - 10.4230/LIPIcs.DISC.2020.54
M3 - Conference contribution
AN - SCOPUS:85109497044
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th International Symposium on Distributed Computing, DISC 2020
A2 - Attiya, Hagit
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 12 October 2020 through 16 October 2020
ER -