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

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

1 Downloads (Pure)

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
Original languageEnglish
Title of host publicationPODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
Place of PublicationNew York, NY.
Pages427–430
Number of pages4
ISBN (Electronic)9781450385480
DOIs
Publication statusPublished - 26 Jul 2021
EventACM Symposium on Principles of Distributed Computing -
Duration: 26 Jul 202130 Jul 2021
https://www.podc.org/

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
Period26/07/2130/07/21
Internet address

Keywords

  • distributed computing
  • topology
  • variants

Cite this