@inproceedings{b2df573eb17b45c4bea5befbb0cd2bbc,
title = "Read-write memory and k-set consensus as an affine task",
abstract = "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.",
keywords = "Immediate snapshot, Iterated affine tasks, Simplicial complexes, k-concurrency, k-set consensus",
author = "Eli Gafni and Yuan He and Petr Kuznetsov and Thibault Rieutord",
note = "Publisher Copyright: {\textcopyright} Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord.; 20th International Conference on Principles of Distributed Systems, OPODIS 2016 ; Conference date: 13-12-2016 Through 16-12-2016",
year = "2017",
month = apr,
day = "1",
doi = "10.4230/LIPIcs.OPODIS.2016.6",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "6.1--6.17",
editor = "Ernesto Jimenez and Panagiota Fatourou and Fernando Pedone",
booktitle = "20th International Conference on Principles of Distributed Systems, OPODIS 2016",
}