Computable obstructions to wait-free computability

We present an algorithmic test for deterministic wait-free solvability of d ecision tasks in asynchronous distributed systems whose processes communica te via read-write shared memory. Input to the test is a formal representati on of the decision task as a triple (I, O, Delta), where I and O are simpli cial complexes specifying the inputs and outputs of the task and Delta is t he 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 o f size at least three. The test is shown to detect the impossibility of wai t-free concensus for all systems, and experimental results show that the te st 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 rema ins open. The key new ingredient underlying the test is a simplicial complex T, the t ask complex, associated to Delta. There is a simplicial projection map a fr om T to I, and a induces a homomorphism alpha(*) from H-* (T) to H-* (I), w hen H-* denotes simplicial hornology. Failure of alpha(*). to surject on H- * (I) implies that no wait-free protocol can solve the task. Put another wa y, the elements of H-* (I) that are not in the image of alpha(*) are obstru ctions to solvability of the task. These obstructions are computable when u sing 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 grou p.