Computable Obstructions to Wait-free Computability
by
John Havlicek
Department of Computer Sciences, University of Texas at Austin

We show how to associate obstructions to a wait-free distributed decision task (I, O, \varDelta) in the asynchronous shared-memory, read-write model. The key new ingredient of this work is the association of a simplicial complex T, the task complex, to the input-output relation \varDelta. There is a simplicial map \alpha from the task complex to the input complex I, and \alpha is determined by the task. The existence of a wait-free protocol solving the task implies that the map \alpha_* induced in homology must surject, and thus the non-zero elements of the cokernel of \alpha_* are obstructions to solvability of the task. These obstructions are effectively computable when using suitable homology theories, such as mod-2 simplicial homology. Functors other than homology can be substituted, although the obstructions obtained may not be computable. We also extend the Herlihy-Shavit 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.

Date received: February 26, 1997

Copyright © 1997 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caao-02.