Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. Why extension-based proofs fail. SIAM Journal on Computing 52(4):913–944, 2023. An earlier version appeared in 51st Annual ACM SIGACT Symposium on Theory of Computing, June 2019, pp. 986–996.
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 or approximate agreement on a cycle of length 4 among n > 2 processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power.
@article{doi:10.1137/20M1375851,
author = {Alistarh, Dan and Aspnes, James and Ellen, Faith and Gelashvili, Rati and Zhu, Leqi},
title = {Why Extension-Based Proofs Fail},
journal = {SIAM Journal on Computing},
volume = {52},
number = {4},
pages = {913-944},
year = {2023},
doi = {10.1137/20M1375851},
URL = {
https://doi.org/10.1137/20M1375851
},
eprint = {
https://doi.org/10.1137/20M1375851
}
,
abstract = { 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 \gt k \geq 2\) processes or approximate agreement on a cycle of length 4 among \(n \gt 2\) processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power. }
}