Locality and Checkability in Wait-free Computing

Abstract. This paper studies several notions of locality that are in-herent 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 pi(t) for a full input s is also a valid output for the partial input pi(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 iso-morphic 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 estab-lishing 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 contain-ing a universal task (induced by the universal covering complex), and at the bottom the trivial identity task