文章基本信息

标题：Locally Solvable Tasks and the Limitations of Valency Arguments
本地全文：下载
作者：Hagit Attiya ; Armando Casta{~n}eda ; Sergio Rajsbaum 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：184
页码：18:1-18:16
DOI：10.4230/LIPIcs.OPODIS.2020.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, implying that there are no local impossibility proofs for these tasks.
关键词：Wait-freedom; Set agreement; Weak symmetry breaking; Impossibility proofs