The Decidability of Distributed Decision Tasks
by
Maurice Herlihy
Computer Science Department, Brown University, Providence RI

A task is a distributed coordination problem in which each process starts with a private input value taken from a finite set, communicates with the other processes by applying operations to shared objects, and eventually halts with a private output value, also taken from a finite set. A protocol is a distributed program that solves a task. A protocol is t-resilient if it tolerates failures by t or fewer processes. A task is solvable in a given model of computation if it has a t-resilient protocol in that model. A set of tasks is decidable in a given model of computation if there exists an effective procedure for deciding whether any task in that set has a t-resilient protocol.

This talk gives necessary and sufficient conditions for task decidability in a range of different models and resilience levels. We prove undecidability by exploiting classical decidability results from algebraic topology, and we prove decidability by explicit construction.

Joint work with Sergio Rajsbaum of U.N.A.M., México.

Date received: July 4, 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-83.