Computable obstructions to wait-free computability

Effectively computable obstructions are associated to a distributed decision task (ℐ,𝒪,Δ) in the asynchronous, wait-free, read-write shared-memory model. The key new ingredient of this work is the association of a simplicial complex 𝒯, the task complex, to the input-output relation d. The task determines a simplicial map α from 𝒯 to the input complex ℐ. The existence of a wait-free protocol solving the task implies that the map α_* induced in homology must surject, and thus elements of H_*(ℐ) that are not in the image of α_*, are obstructions to solvability of the task. These obstructions are effectively computable when using suitable homology theories, such as mod-2 simplicial homology. We also extend Herlihy and Shavit´s Theorem on Spans to the case of protocols that are anonymous relative to the action of a group, provided the action is suitably rigid. For such rigid actions, the quotients of the input complex and the task complex by the group are well-behaved, and obstructions to anonymous solvability of the task are obtained analogously, using the homology of the quotient complexes