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.
翻译:值得庆贺的FLP协商一致的证明中引入了证明分配计算不可能结果的优雅战略。这一战略在每一阶段都是局部性的,考虑一种假定的协商一致协议的配置,同时考虑未来可能的延长期。这一证明战略在与协商一致有关的许多情况下已经使用,使人怀疑为什么没有在另外两项众所周知的任务 -- -- 确定协议和重新命名 -- -- 的不可能结果中加以使用。本文件解释了为什么无法证明这些任务的证据具有全球性质。它表明,从以下意义上讲,协议总是可以在当地解决这类任务。如果选择一个单一的继任配置,那么,协议可以揭示这一执行分支的所有决定,从而满足任务的要求。这一结果既表现为既定协议,也表现为重新命名,意味着这些任务没有当地不可能的证据。