On the Decidability of Distributed Decision Tasks
The Decidability of Distributed Decision Tasks
Maurice Herlihy
Computer Science Department
Brown University
Providence RI 02912
herlihy@cs.brown.edu

Sergio Rajsbaum
Instituto de Matemáticas
U.N.A.M.
Mexico City, D.F. 04510, Mexico
rajsbaum@math.unam.mx

Abstract
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 tresilient if it tolerates failures by t or fewer
processes.
We say that tasks are decidable in a given model of computation if there
exists an effective procedure for deciding whether a task has a tresilient
protocol in that model.
This paper gives the first 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.
Preprint of STOC 97 paper (10 pages),
in Proc. 29th ACM Symp. on the Theory of
Computation (STOC), p. 589598, May 1997.
(the full paper is undergoing revision)
and Maurice Herlihy's
slides.