---
_id: '14364'
abstract:
- lang: eng
  text: 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.
acknowledgement: "We would like to thank Valerie King, Toniann Pitassi, and Michael
  Saks for helpful discussions and Shi Hao Liu for his useful feedback.\r\nThis research
  was supported by the Natural Science and Engineering Research Council of Canada
  under grants RGPIN-2015-05080 and RGPIN-2020-04178, a postgraduate scholarship,
  and a postdoctoral fellowship; a University of Toronto postdoctoral fellowship;
  the National Science Foundation under grants CCF-1217921, CCF-1301926, CCF-1637385,
  CCF-1650596, and IIS-1447786; the U.S. Department of Energy under grant ER26116/DE-SC0008923;
  the European Research Council (ERC) under the European Union’s Horizon 2020 research
  and innovation programme grant agreement 805223 ScaleML; and the Oracle and Intel
  corporations. Some of the work on this paper was done while Faith Ellen was visiting
  IST Austria."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- 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
  id: a2117c59-cee4-11ed-b9d0-874ecf0f8ac5
  last_name: Zhu
citation:
  ama: Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs
    fail. <i>SIAM Journal on Computing</i>. 2023;52(4):913-944. doi:<a href="https://doi.org/10.1137/20M1375851">10.1137/20M1375851</a>
  apa: Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2023).
    Why extension-based proofs fail. <i>SIAM Journal on Computing</i>. Society for
    Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/20M1375851">https://doi.org/10.1137/20M1375851</a>
  chicago: Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi
    Zhu. “Why Extension-Based Proofs Fail.” <i>SIAM Journal on Computing</i>. Society
    for Industrial and Applied Mathematics, 2023. <a href="https://doi.org/10.1137/20M1375851">https://doi.org/10.1137/20M1375851</a>.
  ieee: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based
    proofs fail,” <i>SIAM Journal on Computing</i>, vol. 52, no. 4. Society for Industrial
    and Applied Mathematics, pp. 913–944, 2023.
  ista: Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2023. Why extension-based
    proofs fail. SIAM Journal on Computing. 52(4), 913–944.
  mla: Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” <i>SIAM Journal
    on Computing</i>, vol. 52, no. 4, Society for Industrial and Applied Mathematics,
    2023, pp. 913–44, doi:<a href="https://doi.org/10.1137/20M1375851">10.1137/20M1375851</a>.
  short: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal
    on Computing 52 (2023) 913–944.
date_created: 2023-09-24T22:01:11Z
date_published: 2023-07-25T00:00:00Z
date_updated: 2023-12-13T12:28:29Z
day: '25'
department:
- _id: DaAl
doi: 10.1137/20M1375851
ec_funded: 1
external_id:
  arxiv:
  - '1811.01421'
  isi:
  - '001082972300004'
intvolume: '        52'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1811.01421
month: '07'
oa: 1
oa_version: Preprint
page: 913-944
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '6676'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Why extension-based proofs fail
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2023'
...