Source-linked AI summary
Faster Convergence of Multidimensional Approximate Agreement via Smallest Enclosing Balls
Darya Melnyk
TL;DR
Multidimensional approximate agreement needs practical convergence while preserving convex validity under Byzantine faults. This work proposes BallMidpoint, which uses smallest-enclosing-ball midpoints and achieves a contraction rate of 1/sqrt(2) in synchronous and asynchronous settings.
Problem
Existing multidimensional approximate agreement algorithms can have contraction rates too close to 1 for practical applications, despite needing convergence and convex validity.
Method
BallMidpoint chooses the midpoint of the smallest enclosing ball of local safe areas, with coordinate-free computation in synchronous and asynchronous models.
Results
1/sqrt(2) is achieved as the contraction rate in both synchronous and asynchronous communication models, with a tight 2-dimensional example.
Takeaways & Limitations
The proposed rate is closer to the one-dimensional lower bound of 1/2 than to the upper bound of 1, making multidimensional approximate agreement more suitable for practical applications.
Takeaways & Limitations
In two or more dimensions, a gap remains between the lower bound 1/2 and the achieved contraction rate 1/sqrt(2), and extension to other communication models remains open.
Abstract
from arXiv · showhide
This work considers the multidimensional approximate agreement problem. In this problem, $n$ parties in a distributed system, up to $t$ of which may be corrupted by a Byzantine adversary, need to output vectors that are close to each other and that lie inside the convex hull of all non-corrupted input vectors. We assume that nodes communicate in a fully-connected authenticated network and analyze synchronous and asynchronous communication models. The focus of this work is on the contraction factor of approximate agreement protocols. The first multidimensional approximate agreement protocols had a contraction rate of $1-1/n$(VG, PODC'13) and $\sqrt[d]{1/2}$(MH, STOC'13). While a rate below $1$ is sufficient for convergence, it is not sufficient for practical applications. To date, the best known convergence rate of approximate agreement algorithms is $\sqrt{7/8}\approx0.935$ (FN, DISC'18), which is achieved through the MidExtremes protocol. This stands in contrast to the lower bound on the convergence rate in the $1$-dimensional setting, which is $1/2$. In this work, we propose BallMidpoint - a novel approximate agreement protocol with a contraction rate of $1/\sqrt{2}\approx 0.707$ in the synchronous and the asynchronous communication models. This algorithm satisfies the optimal resilience under convex validity. The presented contraction rate is achieved by choosing the midpoint of the smallest enclosing ball of the so-called local safe areas, and it is tight for the presented algorithms. Similar to (FN, DISC'18), our algorithm is coordinate-free, and the point inside the safe area can be computed efficiently. This work presents the first multidimensional approximate agreement protocol where the convergence rate is closer to the best known lower bound rather than the upper bound of $1$.
1 Introduction
The paper targets practical multidimensional Byzantine approximate agreement under convex validity, proposing BallMidpoint to improve contraction while retaining resilience in synchronous and asynchronous settings.
- 1 Introduction: BallMidpoint chooses the midpoint of the smallest enclosing ball of the safe area as the next-round vector.The smallest enclosing ball is the smallest-radius fully dimensional ball containing the safe area.
- 1 Introduction: The proposed rate improves on the prior 7/8 ≈0.935 contraction rate, bringing convergence closer to the one-dimensional lower bound of 1/2.In one dimension, the algorithms are equivalent to MidExtremes and achieve the optimal contraction rate of 1/2.
- 1 Introduction: 1/√2 contraction is achieved in both synchronous and asynchronous communication models.The contraction bound is shown to be asymptotically tight for both versions of BallMidpoint.
- 1 Introduction: n > max(3, d + 1)t is the synchronous optimal resilience bound, while n > max(3, d + 2)t is required asynchronously.Here, d is the input dimension and t is the upper bound on corrupted nodes.
- 1 Introduction: The convergence proof uses the radius of the smallest enclosing ball of correct inputs, which shrinks by 1/√2 per iteration.The argument relies on selecting a point in the intersection of all safe areas and bounding its distance to their enclosing-ball midpoints.
- 1 Introduction: In asynchronous communication, Gather establishes a common core of n−t accepted vectors, enabling local safe areas to contain a shared global safe area.The common core may include up to t corrupted vectors.
2 Related Work
Multidimensional Byzantine approximate agreement evolved from early protocols with weak or dimension-dependent contraction rates toward coordinate-free methods, while retaining convex validity remains challenging. The paper motivates BallMidpoint against MidExtremes and related smallest-enclosing-ball approaches.
- √(7/8) was the contraction rate established for MidExtremes in static fully connected networks.
- MidExtremes can exceed a 1/2 contraction rate even when computed safe areas intersect, as illustrated by a 20-node construction with four Byzantine nodes.
- 1/2 is the best-known lower bound for multidimensional Byzantine approximate agreement, while later work extended the problem to broader network and validity settings.
- Smallest enclosing balls had already been used for centroid approximation and relaxed validity conditions, but those approaches did not establish the paper’s convex-validity result.
3 Model and Definitions
The model uses authenticated fully connected communication with Byzantine faults under synchronous or asynchronous scheduling, and defines agreement through ball-based proximity and convex-hull containment. Reliable broadcast and Gather align local views while preserving validity and consistency.
- The network is fully connected with authenticated, public, reliable channels, and an adversary may corrupt f < t nodes under worst-case message ordering.
- Synchronous communication has bounded delay and round-based execution, whereas asynchronous communication has unbounded delay and event-based execution.
- Reliable broadcast provides validity, no duplication, consistency, and integrity for synchronously exchanged input vectors.
- Gather creates a common core of n − t values across correct nodes and guarantees validity and consistency, tolerating up to t < n/3 Byzantine nodes.
- MBAA requires correct outputs to lie in a closed ball of radius ε and inside the convex hull of correct inputs.
- The ball-based ε-Agreement definition can allow output diameter up to 2ε, but two additional iterations recover the traditional diameter-ε guarantee.
4 Synchronous multidimensional approximate agreement
Algorithm 3 computes local safe areas from reliably received vectors and chooses each area’s smallest-enclosing-ball midpoint as the next input. Under the stated resilience bound, it achieves a 1/√2 contraction rate, converges logarithmically, and has an asymptotically tight bound.
- Algorithm and definitions: Algorithm 3 computes a safe area from received vectors and selects the midpoint of its smallest enclosing ball.
- Algorithm and definitions: The smallest enclosing ball is unique, and in d dimensions it is defined by at most d + 1 points.
- Convergence: 1/√2 is the per-iteration upper bound on the contraction rate of Algorithm 3 under synchronous communication.
- Correctness: n > max(3, d + 1)t guarantees non-empty safe areas contained in the convex hull of correct vectors.
- Correctness: The ball midpoint lies inside the safe area, ensuring the selected next-round vector preserves the safe-area condition.
- Convergence: O(log√2(1/ε · Rad(Ball(C)))) iterations suffice for the smallest enclosing ball radius to fall below ε.
- Tightness: 1/√2 − δ is achievable in every iteration in a Byzantine construction, establishing asymptotic tightness for Algorithm 3.
5 Asynchronous multidimensional approximate agreement
The asynchronous BallMidpoint algorithm adapts safe-area computation and communication to achieve a contraction rate of 1/√2 under n > max(3, d + 2)t, with an asymptotically tight bound.
- Correctness and convergence: The algorithm solves MBAA when n > max(3, d + 2)t and converges in O(log ...) iterations while maintaining ε-Agreement.The supplied theorem and corollary establish correctness, convergence, and the resilience condition for Algorithm 4.
- Asynchronous algorithm: Gather provides a common core of at least n − t vectors, enabling locally computed safe areas to intersect in the asynchronous setting.Depending on the number of accepted vectors, safe areas use subsets ranging from n − 2t to n − t vectors.
- Asynchronous algorithm: 1/√2 is the contraction-rate upper bound achieved by asynchronous BallMidpoint in every iteration.The algorithm computes the midpoint of the smallest enclosing ball of each locally computed safe area.
- Tightness: The contraction bound is asymptotically tight: a two-dimensional square construction with Byzantine vectors and adversarial views maintains a factor of 1/√2 − δ per iteration.The attack can be repeated in successive iterations as new correct inputs approach side midpoints of the square.
6 Local round estimation
The preprocessing protocols estimate the rounds needed for convergence by exchanging sets that contain all correct vectors, while preserving convex validity and controlling the estimated radius.
- Synchronous communication: The synchronous preprocessing selects the accepted set whose safe-area ball has the largest smallest-enclosing radius to estimate the next iteration.In the worst case, this overestimates the next radius but remains below the smallest-enclosing ball of the correct initial inputs.
- Set acceptance: Every accepted set contains all correct vectors, and every correct node accepts every set originating from a correct node.This is guaranteed by forwarding correct vectors and requiring sufficient set support.
- Radius and validity guarantees: The estimated output radius does not underestimate the radius of the correct outputs and does not overestimate the radius of the correct inputs.The output vectors remain inside the convex hull of the correct input vectors.
- Limitation: The preprocessing contraction rate may exceed 1/√2, but the step takes only a small constant number of rounds and is not expected to significantly affect total convergence time.This is a scope limitation of the preprocessing phase rather than the main iterative contraction guarantee.
- Asynchronous communication: Reliable broadcast is used asynchronously so nodes can rely on received vector sets when constructing safe areas and estimating rounds.Algorithm 6 outputs both a radius estimate and a new input vector for Algorithm 4.
7 Conclusion
The paper presents BallMidpoint for synchronous and asynchronous MBAA, establishes a tight 1/√2 contraction factor, and identifies remaining gaps for multidimensional improvement and broader network models.
- Contributions: BallMidpoint achieves a contraction rate of 1/√2 in both synchronous and asynchronous communication models.The paper also gives a two-dimensional example showing that this bound is tight for the proposed algorithms.
- Open questions: For two or more dimensions, a gap remains between the lower bound 1/2 and the achieved rate 1/√2.The paper leaves improving this multidimensional contraction rate as future work.
- Open questions: The paper also leaves open extension to dynamic and network-agnostic models, where guaranteeing intersection of all safe areas is the main obstacle.These settings involve network assumptions different from the synchronous and asynchronous fully connected models studied here.