Why extension-based proofs fail

D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 986–996.


Conference Paper | Published | English
Author
; ; ; ;
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 - STOC 2019
Page
986-996
Conference
SoCG 2019: Symposium on Computational Geometry
Conference Location
Phoenix, AZ, United States
Conference Date
2019-06-23 – 2019-06-26
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  - STOC 2019. 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  - STOC 2019 (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  - STOC 2019, 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  - STOC 2019, 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 2019. SoCG 2019: Symposium on Computational Geometry 986–996.
Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 986–96, doi:10.1145/3313276.3316407.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1811.01421

Search this title in

Google Scholar
ISBN Search