TY - GEN
T1 - Read-write memory and k-set consensus as an affine task
AU - Gafni, Eli
AU - He, Yuan
AU - Kuznetsov, Petr
AU - Rieutord, Thibault
N1 - Publisher Copyright:
© Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord.
PY - 2017/4/1
Y1 - 2017/4/1
N2 - The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine - it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.
AB - The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine - it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.
KW - Immediate snapshot
KW - Iterated affine tasks
KW - Simplicial complexes
KW - k-concurrency
KW - k-set consensus
UR - https://www.scopus.com/pages/publications/85018302999
U2 - 10.4230/LIPIcs.OPODIS.2016.6
DO - 10.4230/LIPIcs.OPODIS.2016.6
M3 - Conference contribution
AN - SCOPUS:85018302999
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 6.1-6.17
BT - 20th International Conference on Principles of Distributed Systems, OPODIS 2016
A2 - Jimenez, Ernesto
A2 - Fatourou, Panagiota
A2 - Pedone, Fernando
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 20th International Conference on Principles of Distributed Systems, OPODIS 2016
Y2 - 13 December 2016 through 16 December 2016
ER -