Solving Approximate Agreement on continuous and discrete spaces

[2606.23260] Solving Approximate Agreement on continuous and discrete spaces Skip to main content Search Submit Donate Log in Computer Science > Distributed, Parallel, and Cluster Computing arXiv:2606.23260 (cs) [Submitted on 22 Jun 2026 ( v1 ), last revised 22 Aug 2026 (this version, v2)] Title: Solving Approximate Agreement on continuous and discrete spaces Authors: Augustin Albert , Sergio Rajsbaum View PDF HTML (experimental) Abstract: We consider $n$ asynchronous processes prone to crashes, communicating via shared read-write registers, and study the wait-free solvability of approximate agreement: given inputs, processes must output values that are close to each other, and satisfy a validity property. At the very least, if inputs are identical, all outputs must equal that input. The problem has been studied for various input spaces: continuous, discrete, one-dimensional or multidimensional. For metric spaces, validity requires outputs to lie in the convex hull of the inputs. For graphs, and more generally simplicial complexes, several conditions exist. We focus on simplex validity: if inputs span a simplex $\sigma$, then outputs are in $\sigma$. Agreement requires that outputs span a simplex. Solvability depends on the input space, validity condition, and number of processes. For example, the problem is solvable for all $n$ in the plane, but only for $n \leq 2$ when removing a point. For a graph, solvability for $n=2$ holds iff the graph is connected, but $n\geq 3$ requires acyclicity. In the continuous setting, we consider CUB spaces: a broad class of metric spaces admitting a unique convexity definition, subsuming classical $\epsilon$-agreement on $[0,1]$ and $m$-dimensional approximate agreement. Our results show that $\epsilon$-agreement is solvable in every CUB space. In the discrete case, we prove that simplex agreement on a simplicial complex $\mathcal{C}$ is solvable for $n+1$ processes iff $\mathcal{C}$ is $(n-1)$-connected. We discuss several consequences, including a proof of a conjecture by Ledent. Comments: v2, 25 pages, 5 figures Subjects: Distributed, Parallel, and Cluster Computing (cs.DC) Cite as: arXiv:2606.23260 [cs.DC] (or arXiv:2606.23260v2 [cs.DC] for this version) https://doi.org/10.48550/arXiv.2606.23260 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Augustin Albert [ view email ] [v1] Mon, 22 Jun 2026 12:44:11 UTC (52 KB) [v2] Sat, 22 Aug 2026 17:01:30 UTC (56 KB) Full-text links: Access Paper: View PDF HTML (experimental) TeX Source view license Current browse context: cs.DC < prev | next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Solving Approximate Agreement on continuous and discrete spaces#665825
• Solving Approximate Agreement on continuous and discrete spaces#299882
• A statistical evaluation of uncertainty disentanglement methods#464015
• The Temporal Generality Problem#95603
• Continuity of the magnitude for finite metric spaces with nonnegative weightings#799573