arXiv Open Access 2020

An Asynchronous Computability Theorem for Fair Adversaries

Petr Kuznetsov Thibault Rieutord Yuan He

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DC

Penulis (3)

Petr Kuznetsov

Thibault Rieutord

Yuan He

Format Sitasi

APA MLA BibTeX

Kuznetsov, P., Rieutord, T., He, Y. (2020). An Asynchronous Computability Theorem for Fair Adversaries. https://arxiv.org/abs/2004.08348

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓