---
_id: '12566'
abstract:
- lang: eng
  text: "Approximate agreement is one of the few variants of consensus that can be
    solved in a wait-free manner in asynchronous systems where processes communicate
    by reading and writing to shared memory. In this work, we consider a natural generalisation
    of approximate agreement on arbitrary undirected connected graphs. Each process
    is given a node of the graph as input and, if non-faulty, must output a node such
    that\r\n– all the outputs are within distance 1 of one another, and\r\n– each
    output value lies on a shortest path between two input values.\r\nFrom prior work,
    it is known that there is no wait-free algorithm among  processes for this problem
    on any cycle of length , by reduction from 2-set agreement (Castañeda et al.,
    2018).\r\n\r\nIn this work, we investigate the solvability of this task on general
    graphs. We give a new, direct proof of the impossibility of approximate agreement
    on cycles of length , via a generalisation of Sperner's Lemma to convex polygons.
    We also extend the reduction from 2-set agreement to a larger class of graphs,
    showing that approximate agreement on these graphs is unsolvable. On the positive
    side, we present a wait-free algorithm for a different class of graphs, which
    properly contains the class of chordal graphs."
acknowledgement: This project has received funding from the European Research Council
  (ERC) under the European Union’s Horizon 2020 research and innovation programme
  (grant agreement No. 805223 ScaleML) and under the Marie Skłodowska-Curie grant
  agreement No. 840605 and from the Natural Sciences and Engineering Research Council
  of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was
  visiting IST Austria.
article_number: '113733'
article_processing_charge: Yes (via OA deal)
article_type: original
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: Faith
  full_name: Ellen, Faith
  last_name: Ellen
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
citation:
  ama: Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs.
    <i>Theoretical Computer Science</i>. 2023;948(2). doi:<a href="https://doi.org/10.1016/j.tcs.2023.113733">10.1016/j.tcs.2023.113733</a>
  apa: Alistarh, D.-A., Ellen, F., &#38; Rybicki, J. (2023). Wait-free approximate
    agreement on graphs. <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/j.tcs.2023.113733">https://doi.org/10.1016/j.tcs.2023.113733</a>
  chicago: Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate
    Agreement on Graphs.” <i>Theoretical Computer Science</i>. Elsevier, 2023. <a
    href="https://doi.org/10.1016/j.tcs.2023.113733">https://doi.org/10.1016/j.tcs.2023.113733</a>.
  ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement
    on graphs,” <i>Theoretical Computer Science</i>, vol. 948, no. 2. Elsevier, 2023.
  ista: Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on
    graphs. Theoretical Computer Science. 948(2), 113733.
  mla: Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” <i>Theoretical
    Computer Science</i>, vol. 948, no. 2, 113733, Elsevier, 2023, doi:<a href="https://doi.org/10.1016/j.tcs.2023.113733">10.1016/j.tcs.2023.113733</a>.
  short: D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023).
corr_author: '1'
date_created: 2023-02-19T23:00:55Z
date_published: 2023-02-28T00:00:00Z
date_updated: 2025-04-14T07:49:16Z
day: '28'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2023.113733
ec_funded: 1
external_id:
  isi:
  - '000934262700001'
file:
- access_level: open_access
  checksum: b27c5290f2f1500c403494364ee39c9f
  content_type: application/pdf
  creator: dernst
  date_created: 2023-02-20T07:30:20Z
  date_updated: 2023-02-20T07:30:20Z
  file_id: '12570'
  file_name: 2023_TheoreticalCompScience_Alistarh.pdf
  file_size: 602333
  relation: main_file
  success: 1
file_date_updated: 2023-02-20T07:30:20Z
fulldoi: https://doi.org/10.1016/j.tcs.2023.113733
has_accepted_license: '1'
intvolume: '       948'
isi: 1
issue: '2'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '840605'
  name: Coordination in constrained and natural distributed systems
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free approximate agreement on graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 948
year: '2023'
...