---
_id: '6676'
abstract:
- lang: eng
text: "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.\r\n\r\nUsing 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."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
- first_name: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Leqi
full_name: Zhu, Leqi
last_name: Zhu
citation:
ama: '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.3316407'
apa: '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* (pp. 986–996). Phoenix, AZ, United States:
ACM Press. https://doi.org/10.1145/3313276.3316407'
chicago: 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*, 986–96. ACM Press, 2019. https://doi.org/10.1145/3313276.3316407.
ieee: 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.
ista: '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.'
mla: 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.
short: 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.
conference:
end_date: 2019-06-26
location: Phoenix, AZ, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2019-06-23
date_created: 2019-07-24T09:13:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2020-08-11T10:10:40Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3313276.3316407
external_id:
arxiv:
- '1811.01421'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1811.01421
month: '06'
oa: 1
oa_version: Preprint
page: 986-996
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
isbn:
- '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
scopus_import: 1
status: public
title: Why extension-based proofs fail
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...