@inproceedings{6676,
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.},
author = {Alistarh, Dan-Adrian and Aspnes, James and Ellen, Faith and Gelashvili, Rati and Zhu, Leqi},
booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
isbn = {9781450367059},
location = {Phoenix, AZ, United States},
pages = {986--996},
publisher = {ACM Press},
title = {{Why extension-based proofs fail}},
doi = {10.1145/3313276.3316407},
year = {2019},
}