Locality and Checkability in Wait-free Computing

22 pagesThis paper studies several notions of locality that are inherent to the specification of distributed tasks and independent of the computing environment, and investigates the ability of a shared memory wait-free system to solve tasks satisfying various forms of locality. First, we define a task to be projection-closed if every partial output π(t) for a full input s is also a valid output for the partial input π(s) and prove that projection-closed tasks are precisely those tasks that are wait-free checkable. Our second main contribution is dealing with a stronger notion of lo- cality of topological nature. A task T = (I, O, ∆) is said to be locality- preserving if and only if O is a covering complex of I, that is, each simplex s of I is mapped by ∆ to a set of simplexes of O each isomorphic to s. 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. 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