Affine Tasks for k-Test-and-Set

Petr Kuznetsov (1) , Thibault Rieutord (1)

1 Télécom ParisTech

The paper proposes a surprisingly simple characterization of a classical class of models of distributed computing, captured by an affine task : A subcomplex of the second iteration of the standard chromatic subdivision. We show that the class of affine task we propose has an element equivalent, regarding task solvability, to any wait-free shared-memory model in which processes have additionally access to k-test-and-set objects. Our results thus extend existing affine characterization beyond fair models.

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

Petr Kuznetsov, Thibault Rieutord. Affine Tasks for k-Test-and-Set. 2018. ⟨hal-01810601v1⟩