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.
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.