@article{12566,
  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
– all the outputs are within distance 1 of one another, and
– each output value lies on a shortest path between two input values.
From 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).

In 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.},
  author       = {Alistarh, Dan-Adrian and Ellen, Faith and Rybicki, Joel},
  issn         = {0304-3975},
  journal      = {Theoretical Computer Science},
  number       = {2},
  publisher    = {Elsevier},
  title        = {{Wait-free approximate agreement on graphs}},
  doi          = {10.1016/j.tcs.2023.113733},
  volume       = {948},
  year         = {2023},
}