Computable obstructions to wait-free computability
We present an algorithmic test for deterministic wait-free solvability of decision tasks in asynchronous distributed systems whose processes communicate via read-write shared memory. Input to the test is a formal representation of the decision task as a triple (I, O, Delta), where I and O are simplicial complexes specifying the inputs and outputs of the task and Delta is the input-output relation of the task. The form of I, O, and Delta fixes the system size (i.e., number of processes). The result of the test is either (1) that there is no wait-free solution to the decision task for the given system size or (2) inconclusive. Incompleteness of the test is unavoidable since wait-free solvability of decision tasks is undecidable for a system of size at least three. The test is shown to detect the impossibility of wait-free concensus for all systems, and experimental results show that the test detects the impossibility of wait-free set consensus for systems of size at most five. A more complete description of the efficacy of the test remains open. The key new ingredient underlying the test is a simplicial complex T, the task complex, associated to Delta. There is a simplicial projection map a from T to I, and a induces a homomorphism alpha(*) from H-* (T) to H-* (I), when H-* denotes simplicial hornology. Failure of alpha(*). to surject on H-* (I) implies that no wait-free protocol can solve the task. Put another way, the elements of H-* (I) that are not in the image of alpha(*) are obstructions to solvability of the task. These obstructions are computable when using suitable homology coefficients. By passing to quotients of T and I by well-behaved group actions, the test can be adapted to check the impossibility of solution of a decision task by any wait-free protocol that is symmetric or anonymous relative to the group.
wait-free computing decision tasks simplicial complexes homology