# 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, ACM Press, 2019, pp. 986–996.

Download (ext.)

*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

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.3316407Alistarh, 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.3316407Alistarh, 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.### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1811.01421