Brief Announcement: Why Extension-Based Proofs Fail

D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, ACM, 2020, pp. 54–56.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author
Alistarh, Dan-AdrianIST Austria; Aspnes, James; Ellen, Faith; Gelashvili, Rati; Zhu, Leqi
Department
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
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. ACM; 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: ACM. 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. ACM, 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, ACM, 2020, pp. 54–56, doi:10.1145/3382734.3405743.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search