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.
From: Augustin Albert [view email]
[v1]
Mon, 22 Jun 2026 12:44:11 UTC (52 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。