---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  - foaf_Person:
      foaf_givenName: Faith
      foaf_name: Ellen, Faith
      foaf_surname: Ellen
  - foaf_Person:
      foaf_givenName: Joel
      foaf_name: Rybicki, Joel
      foaf_surname: Rybicki
      foaf_workInfoHomepage: http://www.librecat.org/personId=334EFD2E-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-6432-6646
  bibo_doi: 10.1016/j.tcs.2023.113733
  bibo_issue: '2'
  bibo_volume: 948
  dct_date: 2023^xs_gYear
  dct_identifier:
  - UT:000934262700001
  dct_isPartOf:
  - http://id.crossref.org/issn/0304-3975
  dct_language: eng
  dct_publisher: Elsevier@
  dct_title: Wait-free approximate agreement on graphs@
...