The decidability of distributed decision tasks (extended abstract)
Maurice P. Herlihy, Sergio Rajsbaum · 1997
A task is a distributed coordination problem in which each process starts with a private input value taken from a tlnite 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-resikent if it tolerates failures by t or fewer processes.A task is solvable in a given model of computation if it has a t-resilientprotocol 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 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 decidabilit y results from algebraic topology, and we prove decidability by explicit construction.