2026-08-17T19:40:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17642 2024-03-06T11:00:12Z ddc:004 open_access

The Impossibility of Approximate Agreement on a Larger Class of Graphs Liu, Shihao Approximate agreement on graph wait-free solvability triangulated sphere Approximate agreement is a variant of consensus in which processes receive input values from a domain and must output values in that domain that are sufficiently close to one another. We study the problem when the input domain is the vertex set of a connected graph. In asynchronous systems where processes communicate using shared registers, there are wait-free approximate agreement algorithms when the graph is a path or a tree, but not when the graph is a cycle of length at least 4. For many graphs, it is unknown whether a wait-free solution for approximate agreement exists. We introduce a set of impossibility conditions and prove that approximate agreement on graphs satisfying these conditions cannot be solved in a wait-free manner. In particular, the graphs of all triangulated d-dimensional spheres that are not cliques, satisfy these conditions. The vertices and edges of an octahedron is an example of such a graph. We also present a family of reductions from approximate agreement on one graph to another graph. This allows us to extend known impossibility results to even more graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shihao Liu 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.22 urn:nbn:de:0030-drops-176420 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.22 eng https://creativecommons.org/licenses/by/4.0/legalcode