conference paper
Why extension-based proofs fail
published
yes
Dan-Adrian
Alistarh
author 4A899BFC-F248-11E8-B48F-1D18A9856A87
James
Aspnes
author
Faith
Ellen
author
Rati
Gelashvili
author
Leqi
Zhu
author
DaAl
department
STOC: Symposium on Theory of Computing
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 introduce extension-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 solve k-set agreement among n > 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.
ACM Press2019Phoenix, AZ, United States
eng
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
9781450367059
1811.0142110.1145/3313276.3316407
986-996
Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2019). Why extension-based proofs fail. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 986–996). Phoenix, AZ, United States: ACM Press. <a href="https://doi.org/10.1145/3313276.3316407">https://doi.org/10.1145/3313276.3316407</a>
D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Phoenix, AZ, United States, 2019, pp. 986–996.
Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, ACM Press, 2019, pp. 986–96, doi:<a href="https://doi.org/10.1145/3313276.3316407">10.1145/3313276.3316407</a>.
Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2019. Why extension-based proofs fail. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing 986–996.
Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>. ACM Press; 2019:986-996. doi:<a href="https://doi.org/10.1145/3313276.3316407">10.1145/3313276.3316407</a>
D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–996.
Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, 986–96. ACM Press, 2019. <a href="https://doi.org/10.1145/3313276.3316407">https://doi.org/10.1145/3313276.3316407</a>.
66762019-07-24T09:13:05Z2020-08-11T10:10:40Z