Waitfree approximate agreement on graphs
Abstract
Approximate agreement is one of the few variants of consensus that can be solved in a waitfree 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 nonfaulty, 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 waitfree algorithm among $n \ge 3$ processes for this problem on any cycle of length $c \ge 4$, by reduction from 2set agreement (Castañeda 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 2set 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 waitfree algorithm in the nonuniform iterated snapshot model cannot be proved via an extensionbased proof. On the positive side, we present a waitfree algorithm for a class of graphs that properly contains the class of chordal graphs.
 Publication:

arXiv eprints
 Pub Date:
 March 2021
 arXiv:
 arXiv:2103.08949
 Bibcode:
 2021arXiv210308949A
 Keywords:

 Computer Science  Distributed;
 Parallel;
 and Cluster Computing
 EPrint:
 28 pages, 3 figures