论文标题
本地可解决的任务和价值参数的局限性
Locally Solvable Tasks and the Limitations of Valency Arguments
论文作者
论文摘要
在著名的FLP共识不可能证明的情况下，提出了一种证明不可能结果的优雅策略。在每个阶段，这种策略本质上是局部的，考虑到共识的假设方案的一种配置以及可能的扩展价值。这种证明策略已在与共识有关的众多情况下使用，这使一个人想知道为什么在其他两个众所周知的任务的不可能结果中没有使用它：设定协议和重命名。本文解释了为什么这些任务的不可能证明具有全球性质。它表明协议总是可以从以下意义上的本地解决此类任务。给定配置及其所有未来价值，如果选择了单个后继配置，则该协议可以在此执行分支中揭示所有决策，从而满足任务规范。对于设定的协议和重命名，显示了此结果，这意味着这些任务没有本地不可能的证据。
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.
