Brief announcement: Set-consensus collections are decidable

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. In general, however, the question of whether a given task can be solved in a given model of computation is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for a restricted class of models and tasks. We show that the question of whether a collection C of (j, ℓ)-set consensus tasks, for various ℓ (the number of processes that can invoke the task) and j (the number of distinct outputs the task returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n2) decision algorithm, based on a dynamic programming solution to the Knapsack problem. We then present an adaptive wait-free setconsensus algorithm that, for each set of participants, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a model equipped with a collection of set-consensus tasks through its set-consensus power. Therefore, the question of determining the relative power of models defined by set-consensus collections is decidable and, moreover, has an efficient solution.