# 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-Adrian

^{IST Austria}; 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*. ACM; 2020:54-56. doi:10.1145/3382734.3405743Alistarh, 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.3405743Alistarh, 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, 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.