HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

An Asynchronous Computability Theorem for Fair Adversaries

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

Contributor : Thibault Rieutord Connect in order to contact the contributor
Submitted on : Saturday, April 18, 2020 - 11:59:45 AM
Last modification on : Friday, April 9, 2021 - 4:28:05 PM


Files produced by the author(s)


  • HAL Id : hal-01572257, version 4


Petr Kuznetsov, Thibault Rieutord, Yuan He. An Asynchronous Computability Theorem for Fair Adversaries. 2017. ⟨hal-01572257v4⟩



Record views


Files downloads