Faster Convergence of Multidimensional Approximate Agreement via Smallest Enclosing Balls

Faster Convergence of Multidimensional Approximate Agreement via Smallest Enclosing Balls Darya Melnyk1

arXiv:2609.01490v1 [cs.DC] 1 Sep 2026

Abstract 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 multidimensionalpapproximate agreement protocols had a contraction rate of 1 − 1/n(VG, PODC’13) and 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 p rate of approximate agreement algorithms is 7/8 ≈ 0.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/ 2 ≈ 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 socalled 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. Keywords. vector consensus, smallest enclosing ball, convex validity, 1-center

1

Introduction

Many modern distributed applications handle multidimensional data, such as machine learning [22], collaborative learning [13], distributed optimization [25], robot gathering [31], and large-scale elections [29]. In such systems, agreement protocols can be used to aggregate the local vectors into one global output. Exact agreement protocols are, however, either slow (the number of rounds needed is linear in the number of permitted failures), or even impossible (such as asynchronous deterministic agreement with one crash failure). This motivates using approximate agreement algorithms in practical applications. Approximate agreement allows nodes to converge to a common output. The application can thereby define the accuracy of such algorithms, i.e., how close the final vectors should be. In the particular instance of collaborative learning, the problem is equivalent to approximate agreement. To make multidimensional approximate agreement algorithms practical, several properties need to be satisfied: the quality of the agreement vector, the contraction rate, efficient local computability, and resilience. For example, the algorithm that applies one-dimensional approximate agreement in every coordinate is efficient, it has optimal resilience and an optimal contraction rate of 1/2. However, this algorithm is dependent on a fixed coordinate system, and the output vector is only guaranteed to be inside a coordinate-parallel box around the non-corrupted input vectors. In [28], algorithms have been proposed that focus on providing a vector of better quality. In particular, they make sure that the output vectors are inside the convex hull of all non-corrupted 1

melnyk@tu-berlin.de, TU Berlin, Germany

1

input vectors (convex validity). Unfortunately, such algorithms suffer from a resilience that depends on the p dimension of the vectors [28]. Moreover, the best-known contraction rate of such algorithms is 7/8 ≈ 0.935, which is still close to 1, and thus makes the algorithms impractical. In this work, we take a first step towards making multidimensional approximate agreement algorithms that satisfy convex validity more practical. We propose to use the midpoint of the smallest enclosing ball of the safe area to choose a better vector for √ the following round. With this strategy, we receive an algorithm with a contraction rate of 1/ 2, and thus get closer to the best known lower bound of 1/2. This makes the proposed algorithm more suitable to practical applications and mitigates one of its previous drawbacks.

1.1

Our Contribution

In the following, we summarize the contributions of our paper: • We provide the first multidimensional Byzantine approximate agreement algorithm under convex validity for the synchronous all-to-all communication model with authenticated channels that achieves a contraction rate of √12 . This algorithm is based on computing the midpoint of the smallest enclosing ball of the safe area, called BallMidpoint. This algorithm satisfies the optimal resilience bound of n > max(3, d + 1)t, where d is the dimension of the input and t is an upper bound on the number of corrupted nodes. • We extend our results to asynchronous communication, showing that a contraction of √12 can also be achieved in the asynchronous case if n > max(3, d + 2)t. • We show that the contraction rate presented in this paper is asymptotically tight for the synchronous and the asynchronous BallMidpoint algorithms. To this end, we present a worst-case input and Byzantine attack for each communication model. In this construction, the contraction factor remains √12 − δ for each iteration of the BallMidpoint algorithm, where δ is an arbitrarily small constant. • In the case d = 1, our algorithms are equivalent to the MidExtremes algorithm, as the diameter of the points and diameter of the ball are the same in 1D, and thus have an optimal contraction rate of 1/2. In Table 1, we compare the BallMidpoint to other choices of a point inside the safe area. BallMidpoint (this work) contraction rate coordinate-free local time

√1 2

MidExtremes [18] q

MH [27] q

yes O(n2 d)

no O(nd)

7 8

yes O(ndO(d) )2

d

1 2

VG [36] 1 − n1 yes O(nd)

Table 1: Comparison of the results in this paper to prior work. Note that we added the hardness of computing the midpoint of the smallest enclosing ball for a more complete comparison. However, this computation step is not decisive compared to computing the safe area.

1.2

Technical Novelty

In this work, we provide a new algorithm to compute a point in the convex hull of all correct nodes. This algorithm is based on the original algorithm by Mendes et al. [28], where the nodes locally compute a point inside the safe area. In our setting, nodes compute a point inside the intersection of convex hulls of subsets of n − t received vectors. It has later been proven that 2

2 √This result is due to [9]. There also exists a randomized algorithm with an expected runtime of O(d n + d log d) 2 ) [10, 26]. For a fixed d, BallMidpoint is comparable to other choices of a point in the safe area. O(

2

choosing a point inside the safe area is necessary to satisfy convex validity [4]. Thus, in our algorithm, the nodes locally compute the safe areas and choose the midpoint of the smallest enclosing ball of the safe area as the input for the next round. Here, the smallest enclosing ball is a fully-dimensional ball of smallest radius that still contains all vectors in a given set, such as the safe area. The new algorithm idea does not directly imply the improved convergence rate. Additionally, we rely on the property that all safe areas must intersect. This contrasts with previous literature, where only a pairwise intersection of safe areas is used to show convergence. We show that, under synchronous communication, the safe areas must intersect in one point if the nodes use reliable broadcast for communication. To show that all safe areas intersect, we define a global view which contains input vectors for all nodes. This assumption is justified when reliable broadcast is used for communication, as at most one vector will be accepted for any corrupted node. We then show that the safe areas of all local views must contain the global safe area. This proof is based on the fact that each node locally maintains a subset of a global view, and computes the safe areas with potentially fewer sets. To show convergence, we adjust the definition of approximate agreement. Instead of arguing about convergence using the diameter of the vectors, we prove convergence using the radius of the smallest enclosing ball containing all non-corrupted vectors. We show that the radius of this ball shrinks by a factor of √12 in every iteration. This is done by carefully choosing a point in the intersection of all safe areas and upper bounding the distance from this point to the midpoints of the smallest enclosing balls of the safe areas. Under asynchronous communication, the previous argument used in the synchronous case would lead to reduced resilience. We thus rely on Gather [8, 34] to establish reliable communication between the nodes, such that all nodes accept the vectors of a common core of n − t nodes in their local views. The common core may contain up to t corrupted vectors. Using this communication primitive, we can define a global view based on the common core and show that each locally computed safe area will contain the global safe area as a subset. Finally, we emphasize that previously used functions, such as MidExtremes, cannot reach the same contraction bound when using the assumption that the intersection of all safe areas is is √ non-empty. Figure 1 shows an example where the contraction factor of MidExtremes √ 3 3 1 √ 2 ≈ 0.866 > 2 in one iteration, while the contraction factor of BallMidpoint is 3 ≈ 0.577 in the same example.

2

Related Work

Approximate agreement in one dimension was originally introduced by [12] to overcome the FLP impossibility result [16] of distributed computing, which states that no deterministic protocol in the asynchronous communication model that tolerates one crash failure can solve agreement. The idea of relaxing the agreement property has allowed to derive agreement algorithms that not only work in the asynchronous model, but also run in a logarithmic number of rounds in the size of the non-faulty input vectors. The multidimensional setting has been first considered by [28]. The authors propose a solution for multidimensional Byzantine approximate agreement with convex validity. They show lower bounds on the resilience, which are n > max(3, d + 1)f under synchronous communication, and n > max(3, d + 2)f under asynchronous communication. Here, f denotes the actual number of Byzantine nodes in the network. The contraction rate of the algorithms is 1 − 1/n [36] and p d 1/2 [27]. This contraction rate of multidimensional approximate agreement has been first improved in [18], who considered the problem in dynamic networks. The authors provided two algorithms for the dynamic model that have a dimension-independent contraction rate. For one of these algorithms, the MidExtremes, the authors show that p it can also be applied in a static fully-connected network, and has a contraction rate of 7/8. In [19], lower bounds 3

Figure 1: √ This is a construction showing that there can be iterations where MidExtremes has a larger contraction rate than 1/ 2, even if the safe areas computed by the nodes intersect. In this example, there are 20 nodes, four of which are Byzantine. We assume that there are two possible views: in both views, all non-corrupted nodes accept all non-corrupted vectors. Additionally, in one view, the non-corrupted nodes accept the two Byzantine vectors on the left (pink nodes), while in the other view, they accept the two Byzantine vectors on the right (marked yellow). The corresponding safe areas are marked with stripes in the figure. The safe areas form triangles, where two sides are 0.5 long, while the third side is 0.5 + ε, where ε > 0 can be chosen arbitrarily small. Note that the diameter of the non-corrupted input vectors as well as the diameter of their smallest enclosing ball are 1. MidExtremes will choose the midpoint of the longest the new input √ side as √ value, marked with crosses in the figure. Thus, the inputs in the next iteration are at a distance 3/2 > 1/ 2 away from each other. This construction works in the asynchronous communication model in our work. In the case of synchronous communication, one would have to replace the multiplicity of each correct vector to two instead of four nodes, and add a non-corrupted node at the intersection of the two safe areas which does not receive any Byzantine vectors at all.

for approximate agreement have been analyzed in the static and the dynamic settings. There, the 1/2 bound is mentioned as the best-known lower bound for multidimensional Byzantine approximate agreement. Since its introduction, the multidimensional Byzantine approximate agreement problem has been extended to the network-agnostic setting [20, 21], to agreement on graphs [1, 17, 30, 32], and to weaker notions of output quality that do not require convex validity [4–7]. The smallest enclosing balls problem was first introduced in two dimensions in [35], and later formally defined in n-dimensions in [14]. The textbook algorithm for this problem is Welzl’s randomized algorithm [37], which has been extended and improved over the past years for practical applications [9, 10, 15, 24, 26, 38]. In the context of agreement algorithms, the smallest enclosing ball has been used to define centroid approximation[4], as well as a new validity condition [7] for multidimensional protocols. In the latter work, the authors propose agreement algorithms that choose a point inside the smallest enclosing ball of all non-faulty vectors. This validity condition relaxes the convex validity condition. Since only the server aggregates the vectors, no agreement algorithms are considered in that work.

3

Model and Definitions

We consider a fully connected network with n nodes, identified by unique IDs 1, . . . , n. We assume that these IDs are known to all nodes in the network. The nodes communicate via authenticated channels. These channels are public (an eavesdropper can see the messages transmitted over the channel), reliable (a message sent by a node eventually arrives at the destination), and no cryptographic assumptions are made in this work. We assume that the message schedule is worst-case for a given protocol, i.e., an adversary controls the ordering in which the messages arrive. We further assume that the adversary may corrupt f < t of the nodes in the network. Here, f denotes the actual number of failures not known by the system, while t is a known upper bound on the number of failures defined in the algorithm design. In this paper, we refer to the corrupted nodes as faulty or Byzantine and to the non-corrupted nodes as correct nodes.

4

3.1

Communication models

We consider the synchronous and the asynchronous communication models. In the synchronous communication model, the nodes wake up at the same time and start the protocol. The delay of each message sent over the channels is upper bounded by a known constant ∆. We thus design round-based protocols in this model. In each synchronous round, a node can send a message, wait for messages from its neighbors, and perform local computation. In the asynchronous communication model, the message delay is unbounded. Thus, the communication is event-based. Also in the asynchronous communication model, it is possible to define rounds. However, these are defined locally by letting each node attach an iteration number to each message, identifying which iteration number of the algorithm the corresponding message belongs to. Since a Byzantine node, in particular, a crash node, is indistinguishable from a node communicating via links with large message delays, each node can wait for at most n − f messages in a round before proceeding with the next steps. To establish more reliable communication between the nodes, and thus assimilate the nodes’ local views, we will make use of additional communication primitives in both the synchronous and the asynchronous settings that we introduce next. Consistent broadcast for synchronous communication. Under synchronous communication, all correct nodes receive all correct input values in the same round of communication. However, Byzantine nodes have the power to send different messages to different nodes. To avoid this, we use reliable broadcast [2, 33] to transmit messages in this case. Assume that the nodes broadcast their inputs as pairs (i, vi ), where i is the ID of the node, and vi is the corresponding input value. One execution of consistent broadcast[3] as presented in Algorithm 1 provides the following properties while tolerating up to t < n/3 Byzantine nodes: • Validity: If a correct node i broadcasts a message (i, vi ), then every correct process reliably accepts this message eventually. • No duplication: Every correct node reliably accepts at most one message from each sender. • Consistency: If two correct nodes reliably accept the messages (i, vi ) and (i, vi′ ), then, vi = vi′ . • Integrity: If some correct node reliably accepts a message vi with sender i and node i is correct, then vi was previously broadcast by i. Algorithm 1 Synchronous consistent broadcast for n > 3t 1: Each node i ∈ [n] with input value vi executes the following code: 2: 3: 4: 5:

Broadcast (i, vi ) Store all received (j, vj ) in the set Sj Broadcast Si Accept (j, vj ) if (j, vj ) was included in at least n − t many sets Sk

Gather primitive for asynchronous communication. In the asynchronous communication model, we use a stronger broadcast primitive to exchange the messages, called Gather. The original protocol is due to Canetti and Rabin [8]. Algorithm 2 presents the Gather primitive as in [34]. The Gather protocol fulfills the following three properties and can tolerate up to t < n/3 Byzantine nodes: 5

• Common core: There exists a set S of input values of size n − t that is included in the output sets of all correct nodes. • Validity: If a correct node i includes a message (j, vj ) from another correct node j in its output set, then vj is j’s input. • Consistency: If two correct nodes respectively include the messages (i, vi ) and (i, vi′ ) in their output sets, then vi = vi′ . Other than in the synchronous case, we cannot make sure that the common core of n − t values will include correct values only. In the worst case, all t values may come from Byzantine nodes. Algorithm 2 Gather for n > 3t 1: Each node i ∈ [n] with input value vi executes the following code:

Broadcast (i, vi ) reliably. ▷ Using Bracha’s reliable broadcast Wait until n − t messages (j, vj ) have been reliably received and store all accepted messages inside Si 4: Broadcast Si 5: Wait until n − t sets Sj have been accepted. A set Sj is considered accepted if i has S reliably accepted every pair (k, vk ) ∈ Sj . Set Ti = Sj , where Sj is an accepted set 6: Broadcast Ti 7: Wait until n − t sets Tj are accepted. A set Tj is considered accepted if i has reliably S accepted every pair (k, vk ) ∈ Tj . Set Ui = Tj , where Tj is an accepted set 8: return Ui

2:

3:

3.2

Multidimensional Byzantine approximate agreement

In multidimensional Byzantine approximate agreement, the input values of the nodes are vectors v ∈ V . In this work, we assume V to be a finite-dimensional real vector space equipped with an p inner product ⟨·, ·⟩ : V × V → R and the norm ∥x∥ = ⟨x, x⟩. We use d to denote the dimension of V . In practical applications, V is often assumed to be Rd , and the distances are measured in terms of the Euclidean norm. Before providing a formal definition of the problem, we first define the convex hull and a closed ball: Definition 3.1 (Convex set). Let V be a real vector space. A subset W ⊆ V is called a convex set if for any two elements x, y ∈ W and all λ ∈ [0, 1] holds λx + (1 − λ)y ∈ W. Definition 3.2 (Convex hull). A convex hull of a set U ⊆ V , denoted Conv(U ) is the smallest convex set W in V such that U ⊆ W . Definition 3.3 (Closed ball). Let m ∈ V and r ∈ R, r ≥ 0. A closed ball with midpoint in m and radius r is defined as Ball(m, r) = {x ∈ V : ∥x − m∥ ≤ r}. Using these definitions, we can now formally define the multidimensional Byzantine approximate agreement problem. Definition 3.4 (MBAA, adapted version from [28]). A protocol solves the Multidimensional Byzantine Approximate Agreement problem (MBAA) if it satisfies 6

• ε-Agreement: The output vectors of correct nodes should lie inside a d-dimensional closed ball of radius ε. • Containment: The output of all correct nodes must be inside the convex hull of the correct input vectors. • Termination: Each correct node must terminate within a finite amount of time. Note that we adapted the ε-Agreement definition in this work (compared to [28]), such that the nodes must output vectors inside an ε-ball, instead of considering the diameter of the points. We believe a ball-based definition is cleaner for our work, since our algorithms and analysis rely on closed balls. Note that the diameter of the points in our case may be up to 2ε at the time of termination. In contrast, traditional q algorithms that terminate with maximum diameter ε d may lie within a ball of radius r ≤ ε 2(d+1) . This bound is given by Jung’s theorem [23] and is tight if the vectors form a regular d-simplex. Thus, the definition considered here is equivalent to the definition in [28] up to a constant factor ≤ 2. Moreover, the algorithms in this paper satisfy the original definition of MBAA as in [28] if two additional iterations are executed. With a contraction rate of √12 per iteration, this ensures that all correct input vectors are in a ball of radius ε/2, which implies a maximum diameter of ε.

4

Synchronous multidimensional approximate agreement

In this section, we present the synchronous MBAA algorithm. In this algorithm, the nodes exchange their input vectors reliably in every iteration. Based on the received vectors, they locally compute an area where the convex validity is satisfied. As in [28], this is done by computing a so-called safe area on the set of received vectors: Definition 4.1 (Safe area). Let {v1 , . . . , vn } ⊂ V be a set of n vectors. Given ℓ < n, the safe area on ℓ nodes is computed as Safeℓ =

\

Conv {vi , i ∈ I} .

I⊆[n] |I|=ℓ

Note that the safe area in this definition may be empty. Therefore, the safe area in the algorithm is computed on intersections of ℓ = n − t vectors, which guarantees that the safe area is non-empty. In order to choose a point inside the safe area, we use the midpoint of the smallest enclosing ball of the safe area, which is defined as follows: Definition 4.2 (Enclosing ball). Let U ⊆ V . A closed ball Ball(m, r) is an enclosing ball of the set U if U ⊆ Ball(m, r). Definition 4.3 (Smallest enclosing ball). The smallest enclosing ball of a set U ⊆ V , denoted Ball(U ), is an enclosing ball Ball(m∗ , r∗ ) of U such that r∗ ≤ r holds for every enclosing ball Ball(m, r) of U . The smallest enclosing ball has been shown to be unique. Moreover, in d dimensions, the smallest enclosing ball is always defined by at most d + 1 points. We use Rad(Ball(U )) to denote the radius of the smallest enclosing ball of the set U . Definition 4.4 (Ball midpoint). Let U ⊆ V . The ball midpoint of U , denoted BallMidpoint(U ), is the midpoint of Ball(U ).

7

We further define C to be the set of correct input vectors, and Ball(C) to denote the smallest enclosing ball of all correct input vectors. For the following sections, we assume that an upper bound c · Rad(Ball(C)) on the smallest enclosing ball of all correct input vectors is known to all nodes, where c ≥ 1 is some small constant. In Section 6, we discuss how this assumption can be dropped, and how an upper bound on the number of iterations can be computed locally by each node. Algorithm 3 presents the synchronous algorithm solving MBAA as pseudocode. Algorithm 3 Synchronous MBAA with BallMidpoint for n > max(3, d + 1)t 1: Each node i ∈ [n] with input vector vi0 executes the following code:

7:

√
for r = 1, 2, . . . , log2 1ε · c · Rad(Ball(C)) / log2 ( 2) do Consistently broadcast current value vir−1 Store accepted values vjr−1 in Vir−1 = {vjr−1 , j ∈ [n]} vir ← BallMidpoint(Safen−t (Vir−1 )) end for return vir

4.1

Analysis of Algorithm 3

2: 3: 4: 5: 6:

In this section, we analyze the correctness and the contraction rates of Algorithm 3. In particular, we prove the following theorem: Theorem 4.5. Algorithm 3 solves MBAA according to Definition 3.4 in the synchronous
communication setting in log2 1ε · c · Rad(Ball(C)) iterations when n > max(3, d + 1)t, where C is the set of correct input vectors. The contraction rate in every iteration is upper bounded by √12 . We start by proving the correctness of the algorithm. We first make use of the results from Mendes et al. [28] stating that a safe area computed on subsets of n − t vectors is not empty when n > max(3, d + 1)t, and that it is included in the convex hull of all correct vectors. Let C r−1 denote the set of correct vectors vir−1 broadcast in iteration r − 1, where C 0 = C. Let Corr denote the set of IDs of the correct nodes. Lemma 4.6. The safe areas Safen−t (Vir−1 ) computed by each node in Line 5 of Algorithm 3 are non-empty for n > max(3, d + 1)t. Additionally, Safen−t (Vir−1 ) ⊆ Conv(C r−1 ) ∀i ∈ Corr. The proof of this lemma follows directly from the work in [28]. For the non-empty intersection, the authors show that due to the inequality n > max(3, d + 1)t, any d + 1 convex hulls of n − t vectors must intersect. They then apply Helly’s theorem [11] to deduce that all such subsets must have a non-empty intersection. Note that in the original proof, f instead of t was used in the argument, and also the resilience bound was stated with f . The property that the safe area is included in the convex hull of all correct vectors follows from the fact that at least one of the subsets of n − t vectors that are used locally to compute the safe area consists only of correct nodes. Thus, any intersection of the convex hulls will be inside the convex hull of these n − t correct nodes. In the next step, we show that the midpoint of the ball is inside the safe area: Lemma 4.7. The ball midpoint BallMidpoint(Safen−t (Vir−1 )) computed by each node in Line 5 of Algorithm 3 is inside the safe area Safen−t (Vir−1 ) of the respective node. Proof. Let mi := BallMidpoint(Safen−t (Vir−1 )). Assume by means of contradiction that mi ∈ / Safen−t (Vir−1 ). Note that the safe area by definition forms a convex set, as it is the intersection of convex sets. Since mi is not included in the safe area, there exists a hyperplane separating mi from Safen−t (Vir−1 ) that does not include mi . This hyperplane divides the Ball(Safen−t (Vir−1 )) 8

in two spherical caps. We now define B ∗ to be the smallest enclosing ball of the intersection of this hyperplane with the Ball(Safen−t (Vir−1 )). Note that B ∗ has a strictly smaller radius than Ball(Safen−t (Vir−1 )), as it does not include mi . Moreover B ∗ includes the minor spherical cap of Ball(Safen−t (Vir−1 )), and thus the Safen−t (Vir−1 ). This is however a contradiction to Ball(Safen−t (Vir−1 )) being the smallest enclosing ball of the safe area, and thus the theorem statement holds. Note that in [28] it was shown that any algorithm that deterministically chooses a point inside the safe area solves MBAA. The above lemma thus concludes the convergence discussion of our algorithm. It thus remains to show that the contraction rate and the resulting number of iterations to reach the ε-Agreement are as claimed. In the following part, we focus on proving the contraction rate and thus the runtime of the algorithm. Lemma 4.8. All locally computed safe areas Safen−t (Vir−1 ), i ∈ Corr by the correct nodes in an iteration of Algorithm 3 are inside the smallest enclosing ball of all correct vectors in that iteration. That is, Safen−t (Vir−1 ) ⊆ Ball(C r−1 ) ∀i ∈ Corr. Proof. Observe first that Safen−t (Vir−1 ) ⊆ Conv(C r−1 ) ∀i ∈ Corr by Lemma 4.6. By definition of the smallest enclosing ball, we have Conv(C r−1 ) ⊆ Ball(C r−1 ), which concludes the proof. In the next lemma, we show that Ball(C r−1 ) includes a hemisphere of each locally computed ball Ball(Safen−t (Vir−1 )), i ∈ Corr. Note that the intersection of these two balls is already guaranteed by Lemma 4.8. Lemma 4.9. Let m be the midpoint of Ball(C r−1 ), and mi := BallMidpoint(Safen−t (Vir−1 )) denote the midpoint of the smallest enclosing ball of the locally computed safe area of node i. Let − −−m → be the line going through the midpoints of the two balls. Ball(C r−1 ) includes the diameters m, i −−m →. of Ball(Safen−t (Vir−1 )) that are orthogonal to − m, i Proof. We prove the lemma for a fixed correct node i and a fixed iteration r − 1. Observe first that the midpoint of Ball(Safen−t (Vir−1 )) is included in Ball(C r−1 ), because of the combination of Lemma 4.7 and Lemma 4.8. −−m → is included Note next that, if a diameter of Ball(Safen−t (Vir−1 )) that is orthogonal to − m, i r−1 r−1 in Ball(C ), then all orthogonal diameters are included in Ball(C ), and thus a hemisphere of Ball(Safen−t (Vir−1 )) is inside Ball(C r−1 ). This is because any hyperplane in a d-dimensional vector space orthogonal to a line through m intersects a d-dimensional ball Ball(C r−1 ) in either a d − 1-dimensional ball, or a single point, or not at all. Moreover, the midpoint of the d − 1-dimensional ball representing the intersection ball will lie on the line through m. Since −−m →, and a diameter of the ball which is the midpoint of Ball(Safen−t (Vir−1 )) is on the line − m, i − − − → orthogonal to m, mi is included in Ball(C r−1 ), all diameters must be included as well. We first cover two special cases: if the intersection of the two balls is a single point, then Ball(Safen−t (Vir−1 )) degenerates to a single point, and the lemma statement holds. The lemma also holds trivially if Ball(Safen−t (Vir−1 )) ⊆ Ball(C r−1 ). We exclude these two cases for the following analysis. Assume by means of contradiction that none of the diameters of Ball(Safen−t (Vir−1 )) that are −−m → are included in Ball(C r−1 ), i.e., the hyperplane defined by the orthogonal m, orthogonal to − i diameters intersects the boundary of Ball(Safen−t (Vir−1 )) outside of Ball(C r−1 ). Note that all vectors that define Ball(Safen−t (Vir−1 )), which are in the safe area, are inside Ball(C r−1 ) (see Lemma 4.8). In particular, these vectors are inside the intersection Ball(Safen−t (Vir−1 )) ∩ Ball(C r−1 ). Consider the intersection Ball(Safen−t (Vir−1 )) ∩ Ball(C r−1 ). Note that the diameter of this intersection is strictly smaller than the diameter of Ball(Safen−t (Vir−1 )), since the balls are not identical. Therefore, the d-dimensional smallest enclosing ball of this intersection has a 9

smaller radius than Ball(Safen−t (Vir−1 )). Moreover, this ball includes Safen−t (Vir−1 ), meaning that we found an enclosing ball of Safen−t (Vir−1 ) which is smaller than the smallest enclosing ball Ball(Safen−t (Vir−1 )), which is a contradiction. This shows that at least one diameter of −−m → must be inside Ball(C r−1 ) and thus also a whole m, Ball(Safen−t (Vir−1 )) that is orthogonal to − i r−1 hemisphere of Ball(Safen−t (Vi )). We now show one of the main lemmas needed to prove contraction. In this lemma, we show that the safe areas computed by the correct nodes in the same iteration have a non-empty intersection. Lemma 4.10. Let Safen−t (Vir−1 ), i ∈ Corr be the locally computed safe areas by correct nodes in iteration r − 1 of Algorithm 3. Then, Safen−t (Vir−1 ) ̸= ∅.

\ i∈Corr

Proof. Consider iteration r − 1 of Algorithm 3. Note that, under consistent broadcast and in particular its implementation as in Algorithm 1, all correct nodes accept all correct vectors broadcast in this iteration. This reflects the validity property of consistent broadcast. Now consider a global view of the system, where n − f correct and f Byzantine nodes are present. Due to the no duplication property of consistent broadcast, each Byzantine party can have at most one vector accepted by the correct nodes in one consistent broadcast iteration. Using these properties, we will now define a global view. This view corresponds to all accepted vectors (one per sender) in an iteration of the algorithm. Note that there are exactly n − f correct accepted vectors and there can be at most f different Byzantine vectors in this view. We will assume here there are exactly f different Byzantine vectors, and add more deterministically chosen vectors if fewer than f vectors have been broadcast by Byzantine nodes. Let Gr−1 denote this global set of vectors in iteration r − 1. Consider now Safen−t (Gr−1 ), i.e., a globally computed safe area under the assumption that f is not known. By Lemma 4.6, Safen−t (Gr−1 ) ̸= ∅, as G may be the local view of one of the correct nodes. We will show that this safe area is a subset of the local safe area of each correct node, that is Safen−t (Gr−1 ) ⊆ Safen−t (Vir−1 ), ∀i ∈ Corr. The main observation is that every correct node i will accept a subset of the vectors in Gr−1 , i.e., Vir−1 ⊆ Gr−1 ∀i ∈ Corr. This subset includes the n − f correct vectors and potentially fewer Byzantine vectors than in the global view. Consider the convex hulls of subsets of n − t vectors in Gr−1 which are used to compute the global safe area. Note that by the above property, the local safe area Safen−t (Vir−1 ) of a correct node i is computed by intersecting a subset of convex hulls that are used for the computation of the global safe area. Thus, the locally computed safe area always includes the global safe area Safen−t (Gr−1 ). Lemma 4.11. The contraction rate of Algorithm 3 in every iteration is upper bounded by √12 . Proof. Consider iteration r − 1 of the algorithm. Assume for this proof that the midpoint of Ball(C r−1 ) is at the origin O. Note that this can be achieved by translation of the construction, without influencing the distances. Let mi be the midpoints of Ball(Safen−t (Vir−1 )) where i ∈ Corr. Let ρi be the respective radii ρi := Rad(Ball(Safen−t (Vir−1 ))) and let q denote some point inside the intersection of the smallest enclosing balls of the safe areas of all correct nodes, T i.e., q ∈ i∈Corr Ball(Safen−t (Vir−1 )). Such a point exists by Lemma 4.10. Note first that, by definition of q, the following inequality holds: ∥mi − q∥2 ≤ ρ2i

(1)

This is because q is included in every smallest enclosing ball Ball(Safen−t (Vir−1 )) with midpoint in mi . 10

By Lemma 4.9, we know that all diameters of the locally computed balls Ball(Safen−t (Vir−1 )) −−−→ that are orthogonal to O, mi are included in Ball(C r−1 ). Let P := Rad(Ball(C r−1 )) be the radius of the true ball. Then, ∥mi − O∥2 + ρ2i ≤ P2

(2)

This inequality follows by applying the theorem of Pythagoras. Assume that the diameter of −−−→ Ball(Safen−t (Vir−1 )) is orthogonal to O, mi is a chord of Ball(C r−1 ). In this case, the above equation would be satisfied with equality. Since the diameter may be strictly inside Ball(C r−1 ), the distance from the origin to one of the endpoints of the diameter can be upper bounded by the radius of Ball(C r−1 ), giving the above inequality. By adding the inequalities (1) and (2), we get ∥mi − q∥2 + ∥mi ∥2 + ρ2i ≤ P2 + ρ2i . That is, ∥mi − q∥2 + ∥mi ∥2 ≤ P2 .

(3)

We can reformulate the left side as ∥mi − q∥2 + ∥mi ∥2 = ∥mi − q/2 − q/2∥2 + ∥mi − q/2 + q/2∥2 = 2∥mi − q/2∥2 + 2∥q/2∥2 − 2⟨mi − q/2, q/2⟩ + 2⟨mi − q/2, q/2⟩ = 2∥mi − q/2∥2 + ∥q∥2 /2 and rewrite inequality (3) as 2∥mi − q/2∥2 + ∥q∥2 /2 ≤ P2 s

∥mi − q/2∥ ≤

2P2 − ∥q∥2 . 4

The right side of the inequality is maximized for ∥q∥ = 0. We thus get 1 ∥mi − q/2∥ ≤ √ P 2 Note that this provides an upper bound on the distance from any midpoint to the point q/2. That is, there is a ball of radius at most √12 P around q/2 that includes all vir = BallMidpoint(Safen−t (Vir−1 )), which are the input vectors of the correct nodes for the next algorithm iteration. This shows a contraction factor of √12 of the BallMidpoint algorithm under synchronous communication.

Lemma 4.11 showed that the radius of the smallest enclosing ball of all correct vectors shrinks by at least a factor of √12 in each iteration. For the radius to reach below ε, log√2 ( 1ε ·Rad(Ball(C))) iterations of the algorithm are required. This leads to the following corollary: 



Corollary 4.12. Algorithm 3 converges in O log2 1ε · c · Rad(Ball(C)) vectors satisfy ε-Agreement.

11

such that the output

Figure 2: There are 9 correct and 4 Byzantine nodes in this construction. 4 correct vectors form a square, with 5 correct nodes in the middle, and all correct nodes will accept these vectors. Additionally, each correct node at the vertex of the square accepts one of the four Byzantine vectors. The Byzantine vectors are assumed to be placed far away from the correct vectors in the marked direction. The further the placement of the Byzantine vectors, the closer the next input vector of the correct nodes to the midpoint of a side of the square. The safe areas corresponding to the five different views, one of which is just the origin, are marked in the figure. Note that new input vectors of the correct nodes for the next round are also forming a square from points that are close to the midpoints of the sides. Thus, Byzantine nodes can apply an analogous attack in the next iteration.

4.2

Tightness of the contraction bound for Algorithm 3

In this section, we show that the contraction rate is asymptotically tight for Algorithm 3. To this end, we present a construction and a Byzantine attack which shows that the contraction rate of the algorithm can be arbitrarily close to √12 in every iteration of the algorithm. Theorem 4.13. The contraction rate of Algorithm 3 is at least √12 − δ, where δ is an arbitrarily small constant. Proof. Consider a construction in R2 with f ≥ 4 Byzantine and n > 3f correct nodes. For larger d, the same example can be used where all but two dimensions are 0. Place input  vectors of four  1 1 1 1 correct nodes in the vertices of a square, with coordinates √2 , √2 , − √2 , √2 , √12 , − √12 and 



− √12 , − √12 . Place the remaining n − f − 4 correct nodes at the origin. Note that the smallest enclosing ball of the square is 1 in this construction. We now describe the adversarial strategy. Let four Byzantine nodes choose their inputs to be (α, 0), (−α, 0), (0, α) and (0, −α), where α > 2 is a large constant which we will define later. The remaining Byzantine nodes do not broadcast their own input vectors, but may participate in the broadcast of other vectors. Since the Byzantine adversary controls the scheduling of the messages, it is possible for the adversary to make sure that four correct nodes each accept one different input vector from a Byzantine node. The remaining n − f − 4 correct nodes do not accept any Byzantine vectors. The four correct nodes that receive Byzantine inputs receive n − f + 1 values in total and therefore remove one vector to compute the safe areas. The four different safe areas all intersect in the origin. We will refer to these safe areas as the main safe areas. The areas are bounded by the diagonals of the square, and, for α → ∞, they converge to triangles bounded by one side and the two diagonals of the square. The remaining group of n − f − 4 correct nodes has a safe area that contains only the origin. See Figure 2 for an example with 13 nodes. Observe that 12

for α > 2, the midpoints of the smallest enclosing ball of the main safe areas are 

 









√ α ,0 2α+2

,



α α α − √2α+2 , 0 , 0, √2α+2 and 0, − √2α+2 . For the radius of the new smallest enclosing ball of correct vectors, we have √  !   α 1 1 1 2 1 1 1 1 √ = √ · 1− √ =√ · = √ − +O . +O 2 2 α α α2 2α + 2 2 1+ 2 2 α α

Note that we used the Taylor series to expand the second term in the second equality. By choosing α > 1δ , we get that the radius of the smallest enclosing ball after one algorithm iteration is at least √12 − δ. Observe that the inputs for the correct nodes in the next iteration are geometrically the same as in the initial construction up to rotation and scaling (corresponding to the contraction factor). Thus, we can repeat the same attack where the Byzantine nodes rotate their input vectors to (α, α), (−α, α), (α, −α), and (−α, −α). By iteratively repeating this process, we receive an instance where the contraction factor of Algorithm 3 is at least √12 − δ in every iteration.

5

Asynchronous multidimensional approximate agreement

In this section, we present the asynchronous algorithm solving MBAA with a contraction rate of √12 . The procedure is similar to that in the synchronous case, and we will therefore reuse many of the previously stated results. The first difference is that we use the Gather protocol to communicate the vectors in each iteration, as consistent broadcast is not sufficient to guarantee nonempty intersection of all local safe areas. The second difference is the computation of the safe area. In the synchronous case, all nodes receive at least n − t correct vectors. In the asynchronous case, we can only guarantee that the nodes accept a common core of n − t vectors. Additionally, depending on the exact number of accepted vectors, a node can compute a safe area using from n − 2t vectors (if it accepts n − t vectors) up to n − t vectors (if it accepts n vectors). That is, the safe area can be computed by removing subsets of t nodes rather than using subsets of n − 2t nodes. Algorithm 4 presents this idea as pseudocode. As in the synchronous case, we first assume that an upper bound on the smallest enclosing ball of all correct input vectors is known to all nodes, and present the round estimation preprocessing step in Section 6. Algorithm 4 Asynchronous MBAA with BallMidpoint for n > max(3, d + 2)t 1: Each node i ∈ [n] with input vector vi0 executes the following code:

7:

√
for r = 1, 2, . . . , log2 1ε · c · Rad(Ball(C)) / log2 ( 2) do Execute the Gather protocol using current value vir−1 Store all accepted values in Vir−1 = {vjr−1 , j ∈ [n]} Let k := |Vir−1 | − (n − t) vir ← BallMidpoint(Safen−2t+k (Vir−1 )) end for

5.1

Correctness of Algorithm 4

2: 3: 4: 5: 6:

The following theorem states the correctness and runtime of Algorithm 4. Theorem 5.1. Algorithm 4 solves MBAA according to Definition 3.4 in the asynchronous
communication model in log2 1ε · c · Rad(Ball(C)) iterations when n > max(3, d + 2)t, where C is the set of correct input vectors. The contraction rate in every iteration is upper bounded by √12 . We will prove Theorem 5.1 by first focusing on the correctness. Note that the results from Lemma 4.6 and Lemma 4.7 can be extended to the asynchronous setting: 13

Lemma 5.2. The safe areas Safen−2t+k (Vir−1 ) computed by each node in Line 6 of Algorithm 4 are non-empty for n > max(3, d + 2)t. Additionally, Safen−2t+k (Vir−1 ) ⊆ Conv(C r−1 ) ∀i ∈ Corr The proof for this lemma can be derived analogously to the proof of Lemma 4.6. Note that the safe area computation used in Algorithm 4 is analogous to the same step in [28]. Lemma 5.3. The ball midpoint BallMidpoint(Safen−2t+k (Vir−1 )) computed by each node in Line 6 of Algorithm 4 is inside the safe area Safen−2t+k (Vir−1 ) of the respective node. This lemma is identical to Lemma 4.7 and thus the proof of Lemma 4.7 also applies here. This concludes the convergence of Algorithm 4. In the following, we focus on ε-Agreement: Lemma 5.4. All locally computed safe areas Safen−2t+k (Vir−1 ), i ∈ Corr by the correct nodes in an iteration of Algorithm 4 are inside the smallest enclosing ball of all correct vectors in that iteration. That is, Safen−2t+k (Vir−1 ) ⊆ Ball(C r−1 ). The proof of this lemma is analogous to the proof of Lemma 4.8. Also the following lemma can be proven analogously to Lemma 4.9: Lemma 5.5. Let m be the midpoint of Ball(C r−1 ), and mi := BallMidpoint(Safen−2t+k (Vir−1 )) denote the midpoint of the smallest enclosing ball of the locally computed safe area of node i. Let − −−m → be the line going through the midpoint of the two balls. Ball(C r−1 ) includes the diameters m, i −−m →. of Ball(Safen−2t+k (Vir−1 ))) that are orthogonal to − m, i In the following lemma, we show that all locally computed safe areas have a non-empty intersection also in the asynchronous case. Here, the proof differs from the synchronous setting, as the safe areas are computed in a slightly different way. Lemma 5.6. Let Safen−2t+ki (Vir−1 ), i ∈ Corr be the locally computed safe areas by correct nodes in iteration r − 1 of Algorithm 4, where ki := |Vir−1 | − (n − t). Then, \

Safen−2t+ki (Vir−1 ) ̸= ∅.

i∈Corr

Proof. Consider iteration r − 1 of the algorithm. By definition of Gather, there is a common core of at least n − t vectors that is included in every local set Vir−1 . Similar to the proof in the synchronous case, we define a global view Gr−1 . In this case, we define the global view to only contain n − t vectors from the common core. If the common core has a larger number of vectors, we deterministically remove the vectors with the smallest IDs until Gr−1 only has n − t vectors. Let Safen−2t (Gr−1 ) be the global safe area. Note that this set could potentially be the view of a correct node in the protocol, and thus Safen−2t (Gr−1 ) ̸= ∅. We will show that the global safe area is contained in every locally computed safe area. h i n−t+ki
Consider a correct node i with the safe area Safen−2t+ki (Vir−1 ). Let Uℓ , ℓ ∈ n−2t+k i be subsets of n − 2t + ki nodes used to compute the safe area of Vir−1 , and Fλ , λ ∈

h

n−t
n−2t

i

be subsets used to compute the safe area of Gr−1 . Let Di = Vir−1 \ Gr−1 . Consider the sets Uℓ \ Di . We have |Di | ≤ ki as Vir−1 includes the common core and thus also Gk−1 , and therefore |Uℓ \ Di | ≥ n − 2t. Note that Conv(Uℓ \ Di ) ⊆ Conv(Uℓ ) ∀ℓ as the convex hull is computed with potentially fewer vectors. On the other hand, for each set Uℓ , there exists a set Fλ , such that Fλ ⊆ Uℓ \ Di . This is because Gr−1 = Vir−1 \ Di and |Vir−1 \ Di | ≥ n − 2t. T T T Thus Safen−2t (Gr−1 ) = λ Fλ ⊆ ℓ (Uℓ \ Di ) ⊆ ℓ Uℓ = Safen−2t+ki (Vir−1 ). This concludes the proof. Given Lemma 5.6, the contraction rate can be proven: Lemma 5.7. The contraction rate of Algorithm 4 in every iteration is upper bounded by √12 . 14

We omit the proof of this lemma here, as it is analogous to the proof of Lemma 4.11. The contraction lemma leads to the following corollary, which concludes the proof of Theorem 5.1. 

Corollary 5.8. Algorithm 4 converges in O log2 1ε · c · Rad(Ball(C)) vectors satisfy ε-Agreement.

5.2



such that the output

Tightness of the contraction bound for Algorithm 4

In this section, we adapt the construction from Theorem 4.13 to show that the contraction rate is also asymptotically tight for the asynchronous algorithm.

Figure 3: There are 17 correct nodes and 4 Byzantine nodes in this construction. 16 correct vectors form a square, with one correct node in the middle, and all correct nodes will accept these vectors. Additionally, each group of 4 correct nodes accepts one of the four Byzantine vectors. Observe that we could have omitted the correct vector in the middle of the square in this construction. The Byzantine vectors are assumed to be placed far away from the correct vectors in the marked direction. The further the placement of the Byzantine vectors, the closer the next input vector of the correct nodes to the midpoint of a side of the square. The safe areas corresponding to the four different views are marked in the figure. Note that new input vectors of the correct nodes for the next round are also forming a square from points that are close to the midpoints of the sides. Thus, Byzantine nodes can apply an analogous attack in the next iteration.

Theorem 5.9. The contraction rate of Algorithm 4 is at least √12 − δ, where δ is an arbitrarily small constant. Proof. Consider a construction in R2 with n − f ≥ 4f correct and f Byzantine nodes, where f ≥ 4. Note that n ≥ 5f > 3f . For larger d, as in the synchronous case, we can consider vectors where all but two dimensions are 0. We vectors nodes in the  place input   of groups of f correct  1 √1 1 √1 1 1 1 √ √ √ √ √ vertices of a square, with coordinates , 2 , − 2 , 2 , 2 , − 2 and − 2 , − √12 . Note 2 that there are examples, where no correct nodes remain after this assignment. We therefore place the remaining n − 5f correct nodes at the origin, if applicable. Also in this construction, the smallest enclosing ball of the square is 1. For the adversarial strategy, as in the synchronous case, let four Byzantine nodes choose their inputs to be (α, 0), (−α, 0), (0, α) and (0, −α), where α > max( 1δ , 2). The remaining Byzantine nodes do not broadcast any input vectors, but may participate in the broadcast of other vectors. Further, let the adversarial scheduling divide the correct nodes into five views: four groups of f correct nodes accept one Byzantine input vector, but not the three others; The remaining n − 5f correct nodes do not accept any Byzantine vectors. See Figure 3 for an example with 21 nodes. 15

The above groups of f nodes receive n − f + 1 vectors and compute safe areas using subsets of n − 2f + 1 vectors. These safe areas are identical to the safe areas in the proof of Theorem 4.13, and they all intersect in the origin. We refer to these safe areas as the main safe areas. The areas are bounded by the diagonals of the square, and, for α → ∞, they converge to triangles bounded by one side and the two diagonals of the square. The potentially remaining group of n − 5f correct nodes has a safe area that contains only the origin. The rest of the analysis, where the choice of α and the repeated construction in the following iteration is explained, is analogous to the proof of Theorem 4.13.

6

Local round estimation

Similar to [28], we apply the witness technique to estimate the number of rounds at the start of the algorithm. In the following, we differentiate between the synchronous and the asynchronous settings. Synchronous communication. The goal of the round estimation is to receive sets from other nodes that they use to compute the safe areas locally. By choosing the set whose smallest enclosing ball of the safe area is the largest, the nodes in the worst case over-estimate the radius of the smallest enclosing ball of the following iteration, but the value is still below the smallest enclosing ball of the initial inputs of the correct nodes. Algorithm 5 presents this idea as pseudocode. Algorithm 5 Preprocessing: Round estimation, synchronous 1: Each node i ∈ [n] with input vector vi0 executes the following code:

Broadcast vi0 3: Receive vj0 from all nodes and store them in set Si 4: Broadcast Si 5: Accept a vector vj0 , if it is in at least n − t received sets Sj . ▷ all n − f correct vectors will be accepted by i 6: Create a new set Ti that contains all vectors that have been received in at least n − 2t sets Sj . 7: Broadcast Ti 8: Accept other sets Tk if Tk contains all accepted vectors from Line 5 9: Set W = {BallMidpoint(Safen−t (Tk )) : Tk accepted} 10: Set vi′ = BallMidpoint(Safe n−t (W )) m l 1 11: Set roundsi = log2 ( ε · Rad(Ball(W ))) 12: return (vi′ , roundsi ) 2:

The idea of Algorithm 5 is to make sure that the sets Tj that are used to estimate the radius are only accepted, if they contain all correct vectors. Lemma 6.1. Algorithm 5 guarantees that every accepted set Tj by a correct node contains all correct vectors. Additionally, every correct node will accept every set Tj coming from a correct node. Proof. Consider a correct node i. We start by proving that Tk that i accepts in Line 8 contains all correct vectors. Observe that every initially broadcast correct vector will be forwarded by every correct node, and since n − f ≥ n − t, it also ends up in all correct sets Sj . Since every correct node receives every correct set Sj , every correct node will accept every correct vector. This ensures that, even if a set Tb from a Byzantine adversary has been accepted, this set must have contained all n − f correct vectors. 16

We now proceed with the proof that all correct sets Tk will be accepted. Assume that some correct node i accepted a vector vℓ0 . Then, vℓ0 must have appeared in at least n − t sets Sm that i received. At least n − 2t of these sets Sm are from correct nodes and have been received by every correct node. Thus, all correct nodes must have added vℓ0 to their set Tk . In the following, we will use Lemma 6.1 to show that Algorithm 5 produces a suitable round estimation for every correct node. Theorem 6.2. Let C ′ be the set of output vectors vi′ computed by all correct nodes in Algorithm 5. Then, no correct node underestimates the radius of Ball(C ′ ), i.e., Rad(Ball(W )) ≥ Rad(Ball(C ′ )). Moreover, no node overestimates the radius of the ball of the correct input vectors Ball(C), i.e., Rad(Ball(C)) ≥ Rad(Ball(W )). Additionally vi′ are in the convex hull of all correct vectors: vi′ ∈ Conv(C). Proof. We first observe that W always contains at least n − f sets Tk (Lemma 6.1). Moreover, Safen−t (W ) ̸= ∅, since n ≥ |W | ≥ n − f and by a Helly-type applied similarly to Section 4. Note that vi′ is inside Conv(W ). Therefore, Conv(C ′ ) ⊆ Conv(W ), from which Rad(Ball(W )) ≥ Rad(Ball(C ′ )) follows due to the minimality of Ball(C ′ ). For the second part, we show Rad(Ball(C)) ≥ Rad(Ball(W )). The result from Lemma 6.1 says that all accepted sets Tk by a correct node i contain all correct input vectors. Thus, Safen−t (Tk ) is always inside Conv(C), as one of the subsets of n − t vectors used in the safe area computation consists only of correct vectors. Therefore, BallMidpoint(Safen−t (Tk )) ∈ Conv(C) Since this holds for every vector in W , Conv(W ) ⊆ Conv(C) and thus Rad(Ball(C)) ≥ Rad(Ball(W )), and therefore the claim follows. Finally, also vi′ ∈ Conv(C) follows, since all points in W are also in Conv(C) . Note that the contraction rate of the algorithm may be bigger than √12 in this preprocessing step. This step however only requires a small constant number of rounds which would not significantly influence the total convergence time of Algorithm 3. When this preprocessing step is used with Algorithm 3, some nodes may terminate earlier than other. In this case, the nodes can broadcast their final vector and a halt message. This vector can be used as the input of the halted node for the following rounds, together with a set S, which coincides with the local set of the node. Asynchronous communication. In the asynchronous case, we need a stronger communication primitive to make sure that the correct nodes may rely on the sets of vectors that they have received from the Byzantine nodes. To this end, we will replace simple broadcast by reliable broadcast [2]. Algorithm 6 presents this strategy as a pseudocode. Algorithm 6 Preprocessing: Round estimation, asynchronous 1: Each node i ∈ [n] with input vector vi0 executes the following code:

Reliably broadcast vi0 3: Reliably receive vj0 from all nodes and store them in set Si 4: Reliably broadcast Si 5: Wait until n − t sets Sj with |Sj | ≥ n − t have been reliably received and accepted. A set is considered accepted if every vector in Sj has been received reliably. 6: Set W = {BallMidpoint(Safen−2t+kj (Sj )) : Sj accepted kj = |Sj | − (n − t)} 7: Set vi′ = BallMidpoint(Safe n−2t (W )) l m 1 8: Set roundsi = log2 ( ε · Rad(Ball(W ))) 9: return (vi′ , roundsi ) 2:

17

Observe that Algorithm 6 outputs a radius estimate and a new input vector that is used to execute Algorithm 4. Theorem 6.3. Let C ′ be the set of output vectors computed by all correct nodes in Algorithm 6. Then, no correct node underestimates the radius of Ball(C ′ ), i.e., Rad(Ball(W )) ≥ Rad(Ball(C ′ )). Moreover, Rad(Ball(C)) ≥ Rad(Ball(W )). Additionally, vi′ ∈ Conv(C) holds. Proof. We start by showing that no node underestimates the radius of Ball(C ′ ), that is, Rad(Ball(W )) ≥ Rad(Ball(C ′ )) for the set W of every correct node i. Note that Safen−2t (W ) ̸= ∅, because n ≥ |W | ≥ n − t and by a Helly-type applied similarly to Section 5. Observe next that vi′ is the midpoint of the ball of the safe area of W , meaning that vi′ ∈ Conv(W ). By definition of C ′ , vi′ ∈ C ′ ⊆ Conv(C ′ ). Since vi′ ∈ Conv(W ) ∀i ∈ Corr, Conv(C ′ ) ⊆ Conv(W ). Due to the minimality of Ball(C ′ ) we also have Rad(Ball(C ′ )) ≤ Rad(Ball(W )). Next, we show that the computed radius is upper bounded by Rad(Ball(C)). Observe that every BallMidpoint(Safen−2t+kj (Sj )) is inside Ball(C). This is because all the vectors inside the sets Sj have been reliably received by node i, and because |Sj | ≥ n − t, meaning that there is a subset of n − 2t + kj correct vectors that have been used in the construction of the safe area. Since Safen−2t+kj (Sj ) ⊆ Conv(C), the safe area is also inside Ball(C), and with Lemma 5.3 also its midpoint. This holds for all points in W . Therefore, Rad(Ball(C)) ≥ Rad(Ball(W )). Finally, since all points in W are also in Conv(C), BallMidpoint(Safen−2t (W )) = vi′ is also inside Conv(C). This theorem shows that no correct node will under-estimate the number of rounds, and thus the ε-Agreement property can be guaranteed. In the implementation, some correct nodes may run the algorithm longer than others. Therefore, once a node terminates, it needs to initiate or join a reliable broadcast with halt messages and only terminate once it reliably receives n − t halt messages. During this time, a node should continue participating in the reliable communication routines with its final value. Since the safe areas make sure to stay inside the convex hull of all correct vectors of each preceding round, the nodes may not converge further, but they will terminate with ε-Agreement.

7

Conclusion

In this work, we proposed a novel algorithm for the MBAA problem in the synchronous and asynchronous communication models. We showed that a contraction rate of √12 can be achieved in both settings, and we presented a 2-dimensional example, where the contraction bound is tight for the proposed algorithms. Finally, we showed how the nodes can locally estimate the number of rounds based on the given input distribution. There are several interesting questions that remain for future work. The most natural question is whether the contraction rate can be improved even further. Note that in one dimension, the contraction√rate is 1/2 and it is tight. In two or more dimensions, there is still a gap between 1/2 and 1/ 2 that should be investigated further. Another question is whether the algorithm can be extended to other communication models, such as the setting of dynamic networks, or the network-agnostic model. The main obstacle for both settings is to guarantee that all safe areas intersect under different network assumptions.

Acknowledgments This work was supported by the German Research Foundation (DFG), SPP 2378: ReNO-2 (grant 511099228), 2025-2029. The authors acknowledge that ChatGPT was used to generate counterexamples that ruled out several unsuccessful proof attempts for the contraction rate.

18

References [1] D. Alistarh, F. Ellen, and J. Rybicki. Wait-free approximate agreement on graphs. Theoretical Computer Science, 948:113733, 2023. ISSN 0304-3975. doi: https://doi.org/10. 1016/j.tcs.2023.113733. URL https://www.sciencedirect.com/science/article/pii/ S0304397523000464. [2] G. Bracha. Asynchronous Byzantine Agreement Protocols. Information and Computation, 75(2):130–143, 1987. doi: 10.1016/0890-5401(87)90054-X. [3] C. Cachin, R. Guerraoui, and L. Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011. doi: 10.1007/978-3-642-15260-3. [4] M. Cambus and D. Melnyk. Centroid approximation with multidimensional approximate agreement protocols. Theoretical Computer Science, 1080:116044, 2026. ISSN 0304-3975. doi: https://doi.org/10.1016/j.tcs.2026.116044. URL https://www.sciencedirect.com/ science/article/pii/S030439752600294X. [5] M. Cambus, D. Melnyk, T. Milentijević, and S. Schmid. Approximate agreement algorithms for byzantine collaborative learning. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 89–100, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400712586. doi: 10.1145/3694906. 3743343. URL https://doi.org/10.1145/3694906.3743343. [6] M. Cambus, D. Melnyk, T. Milentijević, and S. Schmid. Centroid approximation for byzantine-tolerant federated learning, 2025. URL https://arxiv.org/abs/2506.15264. [7] M. Cambus, D. Melnyk, T. Milentijević, and S. Schmid. Practical validity conditions for byzantine-tolerant federated learning, 2026. URL https://arxiv.org/abs/2605.15887. [8] R. Canetti and T. Rabin. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, page 42–51, New York, NY, USA, 1993. Association for Computing Machinery. ISBN 0897915917. doi: 10.1145/167088.167105. URL https://doi.org/10.1145/167088. 167105. [9] B. Chazelle and J. Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93, page 281–290, USA, 1993. Society for Industrial and Applied Mathematics. ISBN 0898713137. [10] K. L. Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. J. ACM, 42(2):488–499, Mar. 1995. ISSN 0004-5411. doi: 10.1145/201019.201036. URL https://doi.org/10.1145/201019.201036. [11] L. Danzer, B. Grünbaum, and V. Klee. Helly’s theorem and its relatives. In Proc. Sympos. Pure Math., Vol. VII, pages 101–180. Amer. Math. Soc., Providence, RI, 1963. [12] D. Dolev, N. A. Lynch, S. S. Pinter, E. W. Stark, and W. E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33(3):499–516, May 1986. ISSN 0004-5411. doi: 10.1145/5925.5931. URL https://doi.org/10.1145/5925.5931. [13] E. M. El-Mhamdi, S. Farhadkhani, R. Guerraoui, A. Guirguis, L.-N. Hoang, and S. Rouault. Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). In Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/ paper/2021/file/d2cd33e9c0236a8c2d8bd3fa91ad3acf-Paper.pdf. 19

[14] J. Elzinga and D. Hearn. The minimum sphere covering a convex polyhedron. Naval Research Logistics Quarterly, 21(4):715–718, 1974. doi: https://doi.org/10.1002/nav.3800210414. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800210414. [15] K. Fischer, B. Gärtner, and M. Kutz. Fast smallest-enclosing-ball computation in high dimensions. In G. Di Battista and U. Zwick, editors, Algorithms - ESA 2003, pages 630–641, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-39658-1. [16] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, Apr. 1985. ISSN 0004-5411. doi: 10.1145/3149. 214121. URL https://doi.org/10.1145/3149.214121. [17] M. Fuchs, D. Ghinea, Z. Parsaeian, and J. Rybicki. Round and resilience-optimal approximate agreement on trees and block graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’26, page 539–549, New York, NY, USA, 2026. Association for Computing Machinery. ISBN 9798400725128. doi: 10.1145/3796701.3815967. URL https://doi.org/10.1145/3796701.3815967. [18] M. Függer and T. Nowak. Fast Multidimensional Asymptotic and Approximate Consensus. In U. Schmid and J. Widder, editors, 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl – LeibnizZentrum für Informatik. ISBN 978-3-95977-092-7. doi: 10.4230/LIPIcs.DISC.2018.27. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.27. [19] M. Függer, T. Nowak, and M. Schwarz. Tight bounds for asymptotic and approximate consensus. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, page 325–334, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450357951. doi: 10.1145/3212734.3212762. URL https://doi.org/ 10.1145/3212734.3212762. [20] D. Ghinea, C.-D. Liu-Zhang, and R. Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 141–151, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450395458. doi: 10.1145/3558481.3591105. URL https://doi.org/10.1145/3558481.3591105. [21] D. Ghinea, D. Melnyk, and T. Milentijević. Network-agnostic multidimensional approximate agreement with optimal resilience. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’26, page 527–538, New York, NY, USA, 2026. Association for Computing Machinery. ISBN 9798400725128. doi: 10.1145/3796701.3815960. URL https://doi.org/10.1145/3796701.3815960. [22] R. Guerraoui, N. Gupta, and R. Pinot. Byzantine machine learning: A primer. ACM Comput. Surv., 56(7), Apr. 2024. ISSN 0360-0300. doi: 10.1145/3616537. URL https: //doi.org/10.1145/3616537. [23] H. W. Jung. Über die kleinste kugel die eine räumliche figur einschliesst. Journal für die reine und angewandte Mathematik, 123:241–257, 1901. [24] P. Kumar, J. S. B. Mitchell, and E. A. Yildirim. Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Exp. Algorithmics, 8:1.1–es, Dec. 2004. ISSN 1084-6654. doi: 10.1145/996546.996548. URL https://doi.org/10.1145/996546.996548.

20

[25] S. Liu, N. Gupta, and N. H. Vaidya. Approximate byzantine fault-tolerance in distributed optimization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 379–389, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385480. doi: 10.1145/3465084.3467902. URL https://doi.org/ 10.1145/3465084.3467902. [26] J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. In Proceedings of the Eighth Annual Symposium on Computational Geometry, SCG ’92, page 1–8, New York, NY, USA, 1992. Association for Computing Machinery. ISBN 0897915178. doi: 10.1145/142675.142678. URL https://doi.org/10.1145/142675.142678. [27] H. Mendes and M. Herlihy. Multidimensional approximate agreement in byzantine asynchronous systems. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 391–400, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10.1145/2488608.2488657. URL https://doi.org/10.1145/2488608.2488657. [28] H. Mendes, M. Herlihy, N. Vaidya, and V. K. Garg. Multidimensional agreement in byzantine systems. Distributed Computing, 28(6):423–441, 2015. doi: 10.1007/s00446-014-0240-5. [29] A. Naz, B. Piranda, S. C. Goldstein, and J. Bourgeois. Approximate-centroid election in large-scale distributed embedded systems. In 2016 IEEE 30th International Conference on Advanced Information Networking and Applications (AINA), pages 548–556, 2016. doi: 10.1109/AINA.2016.109. [30] T. Nowak and J. Rybicki. Byzantine Approximate Agreement on Graphs. In J. Suomela, editor, 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977126-9. doi: 10.4230/LIPIcs.DISC.2019.29. URL https://drops.dagstuhl.de/entities/ document/10.4230/LIPIcs.DISC.2019.29. [31] D. Pattanayak, K. Mondal, R. H., and P. S. Mandal. Gathering of mobile robots with weak multiplicity detection in presence of crash-faults. Journal of Parallel and Distributed Computing, 123:145–155, 2019. ISSN 0743-7315. doi: https://doi.org/10.1016/j.jpdc.2018.09.015. URL https://www.sciencedirect.com/science/article/pii/S074373151830697X. [32] J. Rybicki and Y. Verbitsky. Solvability of Approximate Agreement on Graphs and Simplicial Complexes. In 41st International Symposium on Distributed Computing (DISC 2026), Leibniz International Proceedings in Informatics (LIPIcs), 2026. [33] T. Srikanth and S. Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80–94, 1987. [34] G. Stern and I. Abraham. Living with asynchrony: the gather protocol, 2021. URL https://decentralizedthoughts.github.io/ 2021-03-26-living-with-asynchrony-the-gather-protocol/. [35] J. J. Sylvester. A question in the geometry of situation. Quarterly Journal of Mathematics, 1:79–86, 1857. [36] N. H. Vaidya and V. K. Garg. Byzantine vector consensus in complete graphs. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, page 65–73, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320658. doi: 10.1145/2484239.2484256. URL https://doi.org/10.1145/2484239.2484256. 21

[37] E. Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, pages 359–370, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. [38] E. A. Yildirim. Two algorithms for the minimum enclosing ball problem. SIAM Journal on Optimization, 19(3):1368–1391, 2008. doi: 10.1137/070690419. URL https://doi.org/10. 1137/070690419.

22

Related documents

• Optimal-diameter partitions into regions of the prescribed measure#1050058
• Information geometric measurements of generalisation#230054
• Optimal mixing of the systematic scan dynamics via approximate tensorization of entropy#972795
• Reimagining Illocutionary Force#752172
• Two Conceptions of Similarity#702088