Locality and checkability in wait-free computing

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers

This paper studies  notions of locality that are inherent to the specification of a
distributed task and independent of the computing environment, in a shared
memory wait-free system.
A  task T =(I,O,D) is checkable if there exists a wait-free distributed algorithm that, given s in I and t in O,  determines whether t in D(s), i.e., if t is a valid output for s according to
the specification D of T. Determining whether a projection-closed task is
wait-free solvable remains undecidable, demonstrating the richness of this
class. A locality property called projection-closed is identified,  that completely characterizes tasks that are wait-free  checkable.
A stronger notion of locality considers tasks  where the outputs look identically to the inputs at every vertex (input value of  a process). A task T =(I,O,D)  is said to be locality-preserving} if  O is a  covering complex of I. This topological property yields obstacles for wait-free  solvability different in nature from the classical agreement impossibility
results. On the other hand, locality-preserving tasks are projection-closed and
therefore always wait-free checkable.  A classification of locality-preserving
tasks in term of their relative computational power is provided.
A correspondence between locality-preserving tasks and subgroups of the edgepath
group of an input complex shows 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.
Guest: Pierre Fraigniaud
Host: Merav Parter