Why extension-based proofs fail
Why extension-based proofs fail
复制标题
为什么基于扩展的证明会失败
DOI：
10.1145/3313276.3316407
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zhu, Leqi
中科院分区：
文献类型：
--
作者：
Alistarh, Dan;Aspnes, James;Ellen, Faith;Gelashvili, Rati;Zhu, Leqi
在异步系统中不可能确定性地解决无等待共识。经典的证明使用一个配价参数，它通过重复扩展有限执行来构造无限执行。我们引入了基于扩展的证明，这是一类不可能性证明，它被建模为证明者和协议之间的交互，并且包含了价参数.使用基于组合拓扑的证明，我们已经证明了不可能以无等待的方式确定性地求解k-set一致性过程n>k≥ 2.然而，不知道是否有可能基于更简单的技术进行证明。我们表明，这种不可能的结果不能得到基于扩展的证明，因此，基于扩展的证明是有限的权力。
It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduceextension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solvek-set agreement amongn>k≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.
登录
查看更多内容
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
Maurice Herlihy;D. Kozlov;S. Rajsbaum
通讯作者：
S. Rajsbaum
立即原子快照和快速重命名（扩展摘要）。
DOI：
--
发表时间：
1993
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
E. Borowsky;E. Gafni
通讯作者：
E. Gafni
无等待计算的简单算法推理表征（扩展摘要）
DOI：
--
发表时间：
1997
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
E. Borowsky;E. Gafni
通讯作者：
E. Gafni
立即原子快照和快速重命名
DOI：
--
发表时间：
1993
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
E. Borowsky;E. Gafni
通讯作者：
E. Gafni
归约和基于扩展的证明
DOI：
--
发表时间：
2021
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Kayman Brusse;Faith Ellen
通讯作者：
Faith Ellen