Set-Consensus Collections are Decidable

Abstract

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 $C$ of \emph{$(\ell ,j)$-set consensus} objects, for various $\ell$ (the number of processes that can invoke the object) and $j$ (the number of distinct outputs the object returns), can be used by $n$ processes to solve wait-free $k$-set consensus is decidable. Moreover, we provide a simple $O(n^2)$ decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an \emph{adaptive} wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using $C$. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its \emph{set-consensus power}.