Brief Announcement: Variants of Approximate Agreement on Graphs and Simplicial Complexes
Jérémy Ledent · 2021
Approximate agreement is a weaker version of consensus where two or more processes must agree on a real number within a distance ε of each other. Many variants of this task have been considered in the literature: continuous or discrete ones; multi-dimensional ones; as well as agreement on graphs and other spaces. We focus on two variants of approximate agreement on graphs, edge agreement and clique agreement. We show that both tasks arise as special cases of a more general, higher-dimensional, approximate agreement task, where the processes must agree on the vertices of a simplex in a given simplicial complex. This new point of view gives rise to a novel topological perspective on the solvability of clique agreement.