Reductions and Extension-Based Proofs
Reductions and Extension-Based Proofs
复制标题
归约和基于扩展的证明
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Faith Ellen
中科院分区：
文献类型：
--
作者：
Kayman Brusse;Faith Ellen
在分布式计算理论中，约简的概念是证明不可能结果的常用工具。如果任务 T 简化为任务 S，并且 T 无法解决，那么 S 也是如此。基于扩展的证明证明了不可能通过构造无限执行以无等待的方式解决任务。众所周知，基于扩展的证明在能力上是有限的：对于 n > k ≥ 2 进程之间的 k 集协议，没有基于扩展的证明来证明 NIS 模型中的无等待协议是不可能的。我们引入了增强的基于扩展的证明，它通过提供一种新型查询来概括基于扩展的证明。对于一般类别的约简，我们证明，如果 T 约简为 S，并且 T 具有基于增强扩展的证明，表明在 NIS 模型中无法求解，那么 S 也是如此。由于对于 n > k ≥ 2 进程之间的 k 集协议，NIS 模型中也没有基于增强扩展的证明，说明无等待协议的不可能性，因此，在用于解决许多其他分布式计算问题的 NIS 模型。
In the theory of distributed computing, the notion of a reduction is a common tool for proving impossibility results. If task T reduces to task S, and T is impossible to solve, then so is S. Extension-based proofs demonstrate the impossibility of solving a task in a wait-free manner by constructing an infinite execution. It is known that extension-based proofs are limited in power: there is no extension-based proof of the impossibility of a wait-free protocol in the NIS model for k-set agreement among n > k ≥ 2 processes. We introduce augmented extension-based proofs, which generalize extension-based proofs by providing a new type of query. For a general class of reductions, we prove that, if T reduces to S, and T has an augmented extension-based proof that it is impossible to solve in the NIS model, then so does S. Since there is also no augmented extension-based proof of the impossibility of a wait-free protocol in the NIS model for k-set agreement among n > k ≥ 2 processes, it follows that there are no (augmented) extension-based proofs of the impossibility of wait-free protocols in the NIS model for a number of other distributed computing problems.
为什么基于扩展的证明会失败
DOI：
10.1145/3313276.3316407
发表时间：
2019
期刊：
51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Alistarh, Dan;Aspnes, James;Ellen, Faith;Gelashvili, Rati;Zhu, Leqi
通讯作者：
Zhu, Leqi