Earlier Version
Why extension-based proofs fail
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.
Download (ext.)
https://arxiv.org/abs/1811.01421
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Alistarh, Dan-AdrianISTA ;
Aspnes, James;
Ellen, Faith;
Gelashvili, Rati;
Zhu, Leqi
Department
Abstract
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.
Publishing Year
Date Published
2019-06-01
Proceedings Title
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
Publisher
ACM Press
Page
986-996
Conference
STOC: Symposium on Theory of Computing
Conference Location
Phoenix, AZ, United States
Conference Date
2019-06-23 – 2019-06-26
ISBN
IST-REx-ID
Cite this
Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM Press; 2019:986-996. doi:10.1145/3313276.3316407
Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2019). Why extension-based proofs fail. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 986–996). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316407
Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 986–96. ACM Press, 2019. https://doi.org/10.1145/3313276.3316407.
D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 986–996.
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, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–96, doi:10.1145/3313276.3316407.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 1811.01421