A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. the model. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection @math of objects, for various @math (the number of processes that can invoke the object) and @math (the number of distinct outputs the object returns), can be used by @math processes to solve wait-free @math -set consensus is decidable. Moreover, we provide a simple @math decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using @math . Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its .
Gafni and Koutsoupias @cite_15 and Herlihy and Rajsbaum @cite_2 showed that wait-free solvability of tasks for @math or more processes using registers is an undecidable question. We show that in a special case of solving set consensus using a set-consensus collection, the question is decidable. Moreover, we give an explicit polynomial algorithm for computing the power of a set-consensus collection.
@cite_15 @cite_2
2042928046 2072035175
We show that no algorithm exists for deciding whether a finite task for three or more processors is wait-free solvable in the asynchronous read-write shared-memory model. This impossibility result implies that there is no constructive (recursive) characterization of wait-free solvable tasks. It also applies to other shared-memory models of distributed computing, such as the comparison-based model. 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.