2026-07-20T05:59:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7076 2024-03-06T10:39:29Z ddc:004 open_access

Set-Consensus Collections are Decidable Delporte-Gallet, Carole Fauconnier, Hugues Gafni, Eli Kuznetsov, Petr Decidability distributed tasks set consensus Knapsack problem 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 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 (l, j)-set consensus objects, for various l (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 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 set-consensus power. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carole Delporte-Gallet and Hugues Fauconnier and Eli Gafni and Petr Kuznetsov 2017 Is Part Of LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2016.7 urn:nbn:de:0030-drops-70761 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode