| Title | An Asynchronous Computability Theorem for Fair Adversaries |
| Publication Type | Conference Paper |
| Year of Publication | 2018 |
| Authors | Kuznetsov, Petr, Rieutord, Thibault, He, Yuan |
| Conference Name | Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-5795-1 |
| Keywords | adversarial models, affine tasks, Computing Theory and Resilience, pubcrawl, Resiliency, topological characterization |
| Abstract | This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and k-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks. |
| URL | http://doi.acm.org/10.1145/3212734.3212765 |
| DOI | 10.1145/3212734.3212765 |
| Citation Key | kuznetsov_asynchronous_2018 |
An Asynchronous Computability Theorem for Fair Adversaries