---
_id: '8382'
abstract:
- lang: eng
  text: We present the first deterministic wait-free long-lived snapshot algorithm,
    using only read and write operations, that guarantees polylogarithmic amortized
    step complexity in all executions. This is the first non-blocking snapshot algorithm,
    using reads and writes only, that has sub-linear amortized step complexity in
    executions of arbitrary length. The key to our construction is a novel implementation
    of a 2-component max array object which may be of independent interest.
article_processing_charge: No
author:
- first_name: Mirza Ahad
  full_name: Baig, Mirza Ahad
  id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
  last_name: Baig
- first_name: Danny
  full_name: Hendler, Danny
  last_name: Hendler
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
- first_name: Corentin
  full_name: Travers, Corentin
  last_name: Travers
citation:
  ama: 'Baig MA, Hendler D, Milani A, Travers C. Long-lived snapshots with polylogarithmic
    amortized step complexity. In: <i>Proceedings of the 39th Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2020:31-40.
    doi:<a href="https://doi.org/10.1145/3382734.3406005">10.1145/3382734.3406005</a>'
  apa: 'Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2020). Long-lived
    snapshots with polylogarithmic amortized step complexity. In <i>Proceedings of
    the 39th Symposium on Principles of Distributed Computing</i> (pp. 31–40). Virtual,
    Italy: Association for Computing Machinery. <a href="https://doi.org/10.1145/3382734.3406005">https://doi.org/10.1145/3382734.3406005</a>'
  chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
    “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” In <i>Proceedings
    of the 39th Symposium on Principles of Distributed Computing</i>, 31–40. Association
    for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3382734.3406005">https://doi.org/10.1145/3382734.3406005</a>.
  ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived snapshots with
    polylogarithmic amortized step complexity,” in <i>Proceedings of the 39th Symposium
    on Principles of Distributed Computing</i>, Virtual, Italy, 2020, pp. 31–40.
  ista: 'Baig MA, Hendler D, Milani A, Travers C. 2020. Long-lived snapshots with
    polylogarithmic amortized step complexity. Proceedings of the 39th Symposium on
    Principles of Distributed Computing. PODC: Principles of Distributed Computing,
    31–40.'
  mla: Baig, Mirza Ahad, et al. “Long-Lived Snapshots with Polylogarithmic Amortized
    Step Complexity.” <i>Proceedings of the 39th Symposium on Principles of Distributed
    Computing</i>, Association for Computing Machinery, 2020, pp. 31–40, doi:<a href="https://doi.org/10.1145/3382734.3406005">10.1145/3382734.3406005</a>.
  short: M.A. Baig, D. Hendler, A. Milani, C. Travers, in:, Proceedings of the 39th
    Symposium on Principles of Distributed Computing, Association for Computing Machinery,
    2020, pp. 31–40.
conference:
  end_date: 2020-08-07
  location: Virtual, Italy
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2020-08-03
date_created: 2020-09-13T22:01:17Z
date_published: 2020-07-31T00:00:00Z
date_updated: 2024-02-28T12:54:30Z
day: '31'
doi: 10.1145/3382734.3406005
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://hal.archives-ouvertes.fr/hal-02860087/document
month: '07'
oa: 1
oa_version: Preprint
page: 31-40
publication: Proceedings of the 39th Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - '9781450375825'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived snapshots with polylogarithmic amortized step complexity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '8383'
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 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 explain why 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
  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
  last_name: Zhu
citation:
  ama: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Brief Announcement:
    Why Extension-Based Proofs Fail. In: <i>Proceedings of the 39th Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2020:54-56.
    doi:<a href="https://doi.org/10.1145/3382734.3405743">10.1145/3382734.3405743</a>'
  apa: 'Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2020).
    Brief Announcement: Why Extension-Based Proofs Fail. In <i>Proceedings of the
    39th Symposium on Principles of Distributed Computing</i> (pp. 54–56). Virtual,
    Italy: Association for Computing Machinery. <a href="https://doi.org/10.1145/3382734.3405743">https://doi.org/10.1145/3382734.3405743</a>'
  chicago: 'Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and
    Leqi Zhu. “Brief Announcement: Why Extension-Based Proofs Fail.” In <i>Proceedings
    of the 39th Symposium on Principles of Distributed Computing</i>, 54–56. Association
    for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3382734.3405743">https://doi.org/10.1145/3382734.3405743</a>.'
  ieee: 'D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Brief Announcement:
    Why Extension-Based Proofs Fail,” in <i>Proceedings of the 39th Symposium on Principles
    of Distributed Computing</i>, Virtual, Italy, 2020, pp. 54–56.'
  ista: 'Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2020. Brief Announcement:
    Why Extension-Based Proofs Fail. Proceedings of the 39th Symposium on Principles
    of Distributed Computing. PODC: Principles of Distributed Computing, 54–56.'
  mla: 'Alistarh, Dan-Adrian, et al. “Brief Announcement: Why Extension-Based Proofs
    Fail.” <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>,
    Association for Computing Machinery, 2020, pp. 54–56, doi:<a href="https://doi.org/10.1145/3382734.3405743">10.1145/3382734.3405743</a>.'
  short: D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings
    of the 39th Symposium on Principles of Distributed Computing, Association for
    Computing Machinery, 2020, pp. 54–56.
conference:
  end_date: 2020-08-07
  location: Virtual, Italy
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2020-08-03
date_created: 2020-09-13T22:01:18Z
date_published: 2020-07-31T00:00:00Z
date_updated: 2024-02-28T12:54:19Z
day: '31'
department:
- _id: DaAl
doi: 10.1145/3382734.3405743
language:
- iso: eng
month: '07'
oa_version: None
page: 54-56
publication: Proceedings of the 39th Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - '9781450375825'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief Announcement: Why Extension-Based Proofs Fail'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...