文章基本信息

标题：Set-Consensus Collections are Decidable
本地全文：下载
作者：Carole Delporte-Gallet ; Hugues Fauconnier ; Eli Gafni 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：70
页码：7:1-7:15
DOI：10.4230/LIPIcs.OPODIS.2016.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Decidability; distributed tasks; set consensus; Knapsack problem