Locality and Checkability in Wait-Free Computing

International audienceA task T is described by a triple (I, O, ∆) where I is the set of input configurations, O is the set of output configurations, and ∆ is the specification of the task mapping every input to a set of possible outputs. We consider notions of locality that are inherent to the task specification, independently from the computational model. We observe that tasks as different as (d + 1)-coloring for degree-d graphs, in the network setting, and consensus, in the wait-free setting, both satisfy the local condition ∆(π(s)) ⊆ π(∆(s)) stating that any output ∆(π(s)) for a partial input π(s) is a partial output π(∆(s)) for the full input s. This property, called monotony, captures locality in a very general sense, independent of the computing environment, by expressing the relationship between the various scales of computation, from the individual processes to the whole system. Unfortunately, monotony is not sufficient to insure efficient computation in the network setting, neither it is sufficient to insure solvability in the wait-free setting. This paper thus investigates other notions of locality which, in the framework of wait-free computing, open up to new, rich classes of tasks. First, we define a task to be projection-closed if π(∆(s)) ⊆ ∆(π(s)), and prove the perhaps surprising fact that projection-closed tasks are precisely those tasks that are wait-free checkable, that is tasks T = (I, O, ∆) for which there exists a wait-free distributed algorithm enabling, given a pair (s, t), s ∈ I, t ∈ O, to check whether t ∈ ∆(s), i.e., to decide whether t is a valid output for s. Our second main contribution is dealing with a stronger notion of locality, where ∆(π(s)) = π(∆(s)). A task T = (I, O, ∆) is said to be locality-preserving if and only if O is a covering complex of I, that is there exists a map p : O → I which agrees with ∆ (i.e., t ∈ ∆(p(t)) for every t ∈ O). This topological property yields obstacles for wait-free solvability different in nature from the classical agreement impossibility results. Apart from the identity task, locality-preserving tasks are not wait-free solvable. On the other hand, localitypreserving tasks are projection-closed, and therefore they are wait-free checkable. We provide a classification of locality-preserving tasks in term of their computational power, by establishing a correspondence between locality-preserving tasks and subgroups of the edgepath group of a complex. Using this correspondence, we prove the existence of hierarchies of locality-preserving tasks, each one containing a universal task (induced by the universal covering complex), and at the bottom the trivial identity task