Fast multidimensional agreement with optimal fault tolerance and ball validity
Fast Multidimensional Approximate Agreement with Optimal Resilience Using Ball Validity
Distributed, Parallel, and Cluster Computing
Summary
When multiple computers or processes try to agree on a shared value in many dimensions, some of them might behave maliciously or unpredictably. This paper proposes new methods that let the honest computers agree on values close to each other without being misled, even if some are faulty. Instead of forcing strict rules on the agreed values, the authors use a flexible geometric approach based on enclosing balls, improving the fault tolerance and speed of agreement. This work also shows limits on these methods and compares them to existing solutions, achieving better guarantees in some cases.
What this means in practice
- •For distributed system engineers: Build distributed systems that reach consensus quickly despite some faulty nodes, using improved multidimensional agreement tolerating maximum faults.
- •For blockchain protocol designers: Implement consensus protocols with optimal fault tolerance and efficient agreement in systems involving multidimensional data inputs.
Authors
Tijana Milentijević, Stefan Schmid
Abstract
Multidimensional approximate agreement requires $n$ processes with inputs in $\mathbb{R}^d$ to output vectors close to each other, despite up to $t$ Byzantine faults. Under convex validity, outputs must lie in the convex hull of the correct inputs, which leads to resilience thresholds that grow with the dimension. We instead study Minimum Enclosing Ball (MEB) validity and its multiplicative relaxation $c$-MEB validity. Our first contribution is Adaptive MEB Contraction, a coordinate-free algorithm that, in the synchronous model with $n>(d+1)t$ contracts the correct MEB radius by $1/\sqrt2$ per round for $α=1$ while satisfying $\sqrt2$-MEB validity. We also give an example showing that this bound is tight for our analysis. Our main technical contribution is a dimension-free inflation theorem: if every $β$ balls in a finite family of Euclidean balls have a common point, then inflating each radius by $\sqrt{β/(β-1)}$ guarantees a common intersection. Applying the theorem to the candidate balls defining the local MEB-safe areas results in a synchronous algorithm with optimal resilience $n>3t$, contraction factor $\sqrt3/2$ and $\sqrt6$-MEB validity. To the best of our knowledge, this is the first multidimensional approximate agreement algorithm with optimal resilience, constant $c$-MEB validity and coordinate-free contraction. We further extend the approach to the asynchronous setting. Without inflation we obtain resilience $n>(d+2)t$, contraction factor $\sqrt{2/3}$ and $\sqrt6$-MEB validity, whereas with inflation for $n>4t$ we get the contraction factor $\sqrt{15}/4$ and $2\sqrt{10}$-MEB validity. Finally, we compare our guarantees with existing algorithms, including Minimum-Diameter Averaging (MDA), for which we derive MEB-validity guarantees. Our algorithms achieve strictly better resilience while providing substantially stronger MEB-validity guarantees than MDA.