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 language | English |
---|---|
Title of host publication | PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing |
Place of Publication | New York, NY. |
Pages | 427–430 |
Number of pages | 4 |
ISBN (Electronic) | 9781450385480 |
DOIs | |
Publication status | Published - 26 Jul 2021 |
Event | ACM Symposium on Principles of Distributed Computing - Duration: 26 Jul 2021 → 30 Jul 2021 https://www.podc.org/ |
Conference
Conference | ACM Symposium on Principles of Distributed Computing |
---|---|
Abbreviated title | PODC |
Period | 26/07/21 → 30/07/21 |
Internet address |
Keywords
- distributed computing
- topology
- variants