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 t-resilient 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 t-resilient 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. 589-598, May 1997. (the full paper is undergoing revision) and Maurice Herlihy's slides.