Brief Announcement: Why Extension-Based Proofs Fail
Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2020. Brief Announcement: Why Extension-Based Proofs Fail. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 54–56.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Alistarh, Dan-AdrianISTA 
;
Aspnes, James;
Ellen, Faith;
Gelashvili, Rati;
Zhu, Leqi
;
Aspnes, James;
Ellen, Faith;
Gelashvili, Rati;
Zhu, LeqiDepartment
Abstract
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. 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 explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.
Publishing Year
Date Published
2020-07-31
Proceedings Title
Proceedings of the 39th Symposium on Principles of Distributed Computing
Page
54-56
Conference
PODC: Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2020-08-03 – 2020-08-07
ISBN
IST-REx-ID
Cite this
Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Brief Announcement: Why Extension-Based Proofs Fail. In: Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2020:54-56. doi:10.1145/3382734.3405743
Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2020). Brief Announcement: Why Extension-Based Proofs Fail. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 54–56). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3382734.3405743
Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Brief Announcement: Why Extension-Based Proofs Fail.” In Proceedings of the 39th Symposium on Principles of Distributed Computing, 54–56. Association for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3405743.
D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Brief Announcement: Why Extension-Based Proofs Fail,” in Proceedings of the 39th Symposium on Principles of Distributed Computing, Virtual, Italy, 2020, pp. 54–56.
Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2020. Brief Announcement: Why Extension-Based Proofs Fail. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 54–56.
Alistarh, Dan-Adrian, et al. “Brief Announcement: Why Extension-Based Proofs Fail.” Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 54–56, doi:10.1145/3382734.3405743.
Google Scholar
ISBN Search