Wait-free approximate agreement on graphs Alistarh, Dan-Adrian ; https://orcid.org/0000-0003-3650-940X Ellen, Faith Rybicki, Joel ; https://orcid.org/0000-0002-6432-6646 ddc:000 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. Elsevier 2023 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/12566 https://research-explorer.ista.ac.at/download/12566/12570 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2023.113733 info:eu-repo/semantics/altIdentifier/issn/0304-3975 info:eu-repo/semantics/altIdentifier/wos/000934262700001 info:eu-repo/semantics/openAccess