Compact Topology of Shared-Memory Adversaries

Petr Kuznetsov (1) , Thibault Rieutord (1) , Yuan He (2)

1 Télécom ParisTech
2 UCLA - University of California [Los Angeles]

The paper proposes a simple topological characterization of a large class of adversarial distributed-computing 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. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

Mots clés: Adversarial models; Affine tasks; Topological characterization

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Petr Kuznetsov, Thibault Rieutord, Yuan He. Compact Topology of Shared-Memory Adversaries. 2017. ⟨hal-01572257v1⟩