@article{14364,
  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 -set agreement among  processes or approximate agreement on a cycle of length 4 among  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.},
  author       = {Alistarh, Dan-Adrian and Aspnes, James and Ellen, Faith and Gelashvili, Rati and Zhu, Leqi},
  issn         = {1095-7111},
  journal      = {SIAM Journal on Computing},
  number       = {4},
  pages        = {913--944},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Why extension-based proofs fail}},
  doi          = {10.1137/20M1375851},
  volume       = {52},
  year         = {2023},
}