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

https://hal.archives-ouvertes.fr/hal-01572257
Contributor : Thibault Rieutord <>
Submitted on : Saturday, April 18, 2020 - 11:59:45 AM
Last modification on : Friday, April 9, 2021 - 4:28:05 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01572257, version 4

Collections

Citation

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

Share

Metrics

Record views

66

Files downloads

83