  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 vertex of the graph as input and, if
non-faulty, must output a vertex 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 $n
\ge 3$ processes for this problem on any cycle of length $c \ge 4$, by
reduction from 2-set agreement (Casta\~neda et al., 2018).
  In this work, we investigate the solvability and complexity of this task on
general graphs. We give a new, direct proof of the impossibility of approximate
agreement on cycles of length $c \ge 4$, 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 on these graphs
is unsolvable. Furthermore, we show that combinatorial arguments, used by both
existing proofs, are necessary, by showing that the impossibility of a
wait-free algorithm in the nonuniform iterated snapshot model cannot be proved
via an extension-based proof. On the positive side, we present a wait-free
algorithm for a class of graphs that properly contains the class of chordal
graphs.
