AI summaryⓘ
The authors study how a group of processes that can fail and communicate through shared memory can agree on values that are close together, called approximate agreement. They focus on different spaces where inputs live, such as continuous spaces, graphs, or simplicial complexes, and the rules that outputs must follow based on the input structure. Their key findings include conditions under which approximate agreement is possible depending on the space and number of processes, such as solvability in connected graphs for two processes and in certain highly connected complexes for more processes. They also identify a broad class of metric spaces, called CUB spaces, where approximate agreement can always be solved. Their work helps clarify when such agreement tasks are possible in complex settings and confirms a previously stated conjecture by Ledent.
approximate agreementwait-free solvabilityshared memorysimplicial complexconvex hullmetric spaceCUB spaceconnectivityprocess crashesdistributed computing
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 $σ$, then outputs are in $σ$. 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 $ε$-agreement on $[0,1]$ and $m$-dimensional approximate agreement. Our results show that $ε$-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.