Locality and checkability in wait-free computing

International audienceThis paper studies notions of locality that are inherent to the specification of distributed tasks %, and independent of the computing model, by identifying fundamental relationships between the various scales of computation, from the individual process to the whole system. A locality property called \emph{projection-closed} is identified. This property completely characterizes tasks that are wait-free \emph{checkable}, where a task $T =(\m{I},\m{O},\Delta)$ is said to be checkable if there exists a distributed algorithm that, given $s\in\m{I}$ and $t\in\m{O}$, determines whether $t\in\Delta{(s)}$, i.e., whether $t$ is a valid output for $s$ according to the specification of $T$. Projection-closed tasks are proved to form a rich class of tasks. In particular, determining whether a projection-closed task is wait-free solvable is shown to be undecidable. A stronger notion of locality is identified by considering tasks whose outputs ''look identical'' to the inputs at every process: a task $T= (\m{I},\m{O},\Delta)$ is said to be \emph{locality-preserving} if $\m{O}$ is a covering complex of $\m{I}$. We show that this topological property yields obstacles for wait-free solvability different in nature from the classical impossibility results. On the other hand, locality-preserving tasks are projection-closed, and thus they are wait-free checkable. A classification of locality-preserving tasks in term of their relative computational power is provided. This is achieved by defining a correspondence between subgroups of the \emph{edgepath} group of an input complex and locality-preserving tasks. This correspondence enables to demonstrate the existence of hierarchies of locality-preserving tasks, each one containing, at the top, the universal task (induced by the universal covering complex), and, at the bottom, the trivial identity task