Brief announcement : variants of approximate agreement on graphs and simplicial complexes

Ledent, Jérémy; (2021) Brief announcement : variants of approximate agreement on graphs and simplicial complexes. In: PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. ACM, New York, NY., 427–430. ISBN 9781450385480 (https://doi.org/10.1145/3465084.3467946)

[thumbnail of Ledent-ACS2021-variants-of-approximate-agreement-on-graphs]
Preview
 Text. Filename: Ledent_ACS2021_variants_of_approximate_agreement_on_graphs.pdf
Accepted Author Manuscript
Download (606kB)| Preview

Abstract

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

CORE (COnnecting REpositories)