The concept of extension-based proofs models the idea of a valency argument which is widely used in distributed computing. Extension-based proofs are limited in power: it has been shown that there is no extension-based proof of the impossibility of a wait-free protocol for $(n,k)$-set agreement among $n > k \geq 2$ processes. A discussion of a restricted type of reduction has shown that there are no extension-based proofs of the impossibility of wait-free protocols for some other distributed computing problems. We extend the previous result to general reductions that allow multiple instances of tasks. The techniques used in the previous work are designed for certain tasks, such as the $(n,k)$-set agreement task. We give a necessary and sufficient condition for general colorless tasks to have no extension-based proofs of the impossibility of wait-free protocols, and show that different types of extension-based proof are equivalent in power for colorless tasks. Using this necessary and sufficient condition, the result about reductions can be understood from a topological perspective.
翻译:摘要:扩展性证明的概念模拟了分布式计算中广泛使用的完整性参数。扩展性证明的动力受到限制:已证明在$n>k\geq 2$个进程之间不存在$(n,k)$-元素协议的扩展性证明。前人研究局限于一种受限制的归约类型,并表明对于其他分布式计算问题的无等待协议的不可能性,不存在扩展型证明。我们将先前的结果扩展到允许多个实例任务的一般归约。前人的技术是针对某些任务设计的,如$(n,k)$-元素协议任务。我们给出彩色任务没有扩展型证明不可能性的必要和充分条件,并表明扩展型证明的不同类型对于无色任务来说是等价的功率。利用这个必要和充分的条件,归约的结果可以从拓扑角度来理解。