arXiv CSopen access

Fast Multidimensional Approximate Agreement with Optimal Resilience Using Ball Validity

· arxiv_cs

arXiv CS · Papers · License: Open Access

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Fast Multidimensional Approximate Agreement with Optimal Resilience Using Ball Validity Tijana Milentijević1 and Stefan Schmid1,2 1

arXiv:2609.07599v1 [cs.DC] 7 Sep 2026

TU Berlin Weizenbaum Institute

Abstract Multidimensional approximate agreement is a fundamental task in distributed computing. It requires n processes with inputs in Rd to output vectors that are close to each other despite up to t Byzantine faults being present. For the widespread convex validity the output must lie in the convex hull of the correct vectors. Although this guarantee is strong in theory, it becomes prohibitive in high-dimensional scenarios, because the required resilience threshold grows with the dimension. We therefore study the approximate agreement problem under Minimum Enclosing Ball (MEB) validity, which has so far been considered for vector consensus in the literature. It requires every output to lie within the radius of the minimum enclosing ball of the correct inputs. We also present the c-MEB relaxed validity, where the agreement is within the MEB with its radius scaled by c. Our first contribution is the Adaptive MEB Contraction Algorithm, which is coordinate-free √ and fast: it contracts the correct MEB radius by 1/ 2 ≈ 0.707 per round in the synchronous √ model with n > (d + 1)t, while satisfying 2-MEB validity. We also provide an example which shows that this contraction factor cannot be improved. Our main technical contribution is a new dimension-free ball inflation theorem. We prove that if every β p balls of a finite family of Euclidean balls have a common point, then inflating every radius by β/(β − 1) makes the whole family intersect. Applying the theorem to the candidate balls defining the local √ MEB-safe √ areas results in a synchronous algorithm with resilience n > 3t, contraction factor 3/2 and 6-MEB validity. To the best of our knowledge, this is the first multidimensional approximate agreement algorithm with optimal resilience n > 3t that satisfies constant c-MEB validity and contracts by a factor independent of the dimension. We further extend the approach to the asynchronous setting, using the Gatherpprotocol. We √ obtain an algorithm that achieves resilience n > (d + 2)t, has contraction factor√ 2/3 and √6-MEB validity, and its inflated variant with resilience n > 4t, contraction factor 15/4 and 2 10-MEB validity. Finally, we compare our guarantees with existing approximate agreement and contraction 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.

Introduction

Agreement is an important task in distributed systems because different components often need to make consistent decisions. In many applications, the processes agree on numerical or geometric values. Examples include sensor measurements [8], clock corrections [30], gradients in distributed learning [13, 14, 22, 40]. In such settings, insisting on exact agreement is, however, often unnecessary, 1

since it is enough that the outputs of the correct processes are sufficiently close to each other. This relaxation is referred to as approximate agreement, first introduced in [21]. In approximate agreement, each of the n processes starts with an input value, and up to t processes may be Byzantine, meaning that they can behave arbitrarily and omit messages. The goal of approximate agreement is that all correct processes eventually output values that are within distance ε from each other. At the same time, the output must satisfy a validity condition, i.e. a geometric guarantee which prevents Byzantine processes from pulling the output arbitrarily far away from the values proposed by correct processes. In this work, we study the multidimensional setting, where the inputs are vectors in Rd . The standard validity condition for multidimensional approximate agreement is convex validity: every correct output must lie in the convex hull of the correct input vectors. Convex validity provides a strong theoretical guarantee, but it has a fundamental drawback in higher dimension. Its resilience n > (d + 1)t in the synchronous and n > (d + 2)t in the asynchronous setting depends on the dimension d. Thus, when the dimension is large compared to the number of processes n, convex validity severely limits the number of Byzantine faults that can be tolerated. This motivates the following question: Can we obtain multidimensional approximate agreement with dimension-free resilience while preserving a constant geometric validity guarantee? We answer this question affirmatively using minimum enclosing balls. Instead of requiring outputs to remain in the convex hull of the correct inputs, we require them to remain close to the minimum enclosing ball of the correct inputs. This gives a weaker validity condition, however it allows us to achieve resilience independent of dimension d. Our goal is not only to achieve a reasonable validity notion, but also to obtain fast convergence. Since approximate agreement is iterative, in every round, each correct process computes a new value, and these new values become the inputs to the next round. Hence, agreement requires a contraction argument showing that the region containing all correct values shrinks over time. We measure this shrinkage by the radius of the minimum enclosing ball of the correct values and design algorithms that shrink this radius directly rather than shrinking one coordinate at a time. This makes the contraction factor independent of the dimension.

1.1

Our Contributions

We study multidimensional approximate agreement under Byzantine faults through the lens of minimum enclosing balls. Instead of requiring all correct outputs to remain in the convex hull of the correct inputs, we use the weaker but still geometric notion of c-MEB validity, i.e. all correct outputs must remain within a factor c of the minimum enclosing ball of the initial correct values. This relaxation allows us to go beyond the n > (d + 1)t resilience barrier of convex validity while preserving coordinate-free convergence guarantees. Our first contribution is the Adaptive MEB Contraction Algorithm, a coordinate-free update rule that contracts the radius of the minimum enclosing ball of the correct values. In the synchronous √ setting with n > (d + 1)t, the algorithm achieves contraction factor 1/ 2 for α = 1 and satisfies √ 2-MEB validity. More generally, the parameter α provides a tradeoff between local computation and contraction quality. The case α = 1 gives the strongest contraction guarantee in this paper. For p comparison, MidExtremes, contracts the diameter of correct values by 7/8 ≈ 0.935, whereas our √ algorithm contracts the radius of the minimum√enclosing ball around correct values by 1/ 2 ≈ 0.707. We also give an example showing that the 1/ 2 factor cannot be improved within our contraction analysis. 2

Algorithm MidExtremes [24]

Resilience

Validity

non-split

convex

round model

(⇒ 1-MEB)

√ 2-MEB

Adaptive MEB Contr. Alg. 1, α = 1

MDA [22]

n > (d + 1)t Thm. 5.1, Cor. 5.2 n > 4t

Inflated Alg. 1, α = 1

n > 3t

[24]

✓

Lem. 4.1

✓

√ Rr+1 ≤ 1/ 2Rr Dr+1 ≤ 2/3Dr

Lem. 7.2

[12]

Thm. 5.6, Cor. 5.7

Coord.

7/8Dr

7-MEB √ 6-MEB

Inflated Adaptive MEB Contr.

Contraction Dr+1 ≤

Rr+1 ≤

√

✓ 3/2Rr

Lem. 5.5

✓

Table 1: Comparison of synchronous and round-based multidimensional approximate-agreement algorithms. Here Rr denotes the radius of the minimum enclosing ball of the correct values in round r, while Dr denotes their diameter. For our algorithms, α = 1. The last column indicates whether the algorithm is coordinate-free. The MidExtremes is stated for the non-split network model, in which any two processes have a common incoming neighbor, rather than for the Byzantine consistent broadcast model we use. Note that convex validity implies 1-MEB validity. Our main contribution is a dimension-free ball inflation theorem. We prove that if every subfamilypof at most β Euclidean balls has a common point, then inflating every radius by a factor of β/(β − 1) guarantees that the entire family intersects. This result lets us apply the same contraction idea even when the candidate MEB balls do not intersect necessarily, that is the case with n ≤ (d + 1)t. In the synchronous setting, this gives √ √ an inflated algorithm with optimal resilience n > 3t, contraction factor 3/2 for α = 1, and 6-MEB validity. To the best of our knowledge this is the first multidimensional approximate agreement algorithm achieving the optimal resilience n > 3t with coordinate-free contraction, while still satisfying a meaningful geometric validity condition. The threshold n > 3t is optimal for Byzantine agreement. Our next contribution extends the approach to the asynchronous setting using the Gather protocol. Without inflation, we obtain an asynchronous algorithm for n > (d + 2)t with contraction factor √ p 2/3 and 6-MEB validity for α = 1. With√inflation, we √ obtain a dimension-free asynchronous algorithm for n > 4t with contraction factor 15/4 and 2 10-MEB validity. Finally, we compare our guarantees with prior multidimensional approximate agreement algorithms. The algorithms contract different properties: Mendes–Herlihy algorithm contracts coordinate-wise ranges, while MidExtremes and MDA contract the diameter of correct values. Our algorithms contract the radius of the minimum enclosing ball of correct values. To compare MDA under the same validity notion, we derive the MEB-validity guarantees. Tables 1 and 2 summarize the resulting guarantees in the synchronous and asynchronous settings. Here, two resilience bounds emerge. At the convex validity thresholds n > (d + 1)t and n > (d + 2)t in the synchronous and asynchronous model, respectively, achieve smaller dimension-independent √ √ contraction factors, though for the radius contraction, at the price of satisfying 2- and 6-MEB validity. Below those thresholds, where convex validity cannot be achieved, ball inflation extends the same algorithms to resilience n > 3t and n > 4t, with weaker but constant contraction and with better validity constants than MDA achieves at worse resilience. We next give the main technical ideas behind these results.

1.2

Technical Overview

We consider a fully connected network of n processes, where at most t are Byzantine, in two communication models. In the synchronous model, computation is carried out in rounds and every process consistently broadcasts its current value, so all correct processes receive all correct values. 3

Algorithm

Resilience

Contraction

convex

∆r+1 ≤ 2−1/d ∆(m) r

(⇒ 1-MEB)

[35]

n > (d + 2)t

convex MidExtremes [24]

n > (d + 2)t

Adaptive MEB Contr. Alg. 2, α = 1

MDA [22]

[24]

√ 6-MEB

11-MEB

n > 7t n > 4t

Dr+1 ≤

(⇒ 1-MEB)

n > (d + 2)t Thm. 6.2, Cor. 6.3 Lem. 7.2

√ 2 10-MEB

Inflated Adaptive MEB Contr. Inflated Alg. 2, α = 1

Coord.

(m)

Mendes–Herlihy [35]

Validity

Thm. 6.6, Cor. 6.7

Rr+1 ≤

× 7/8Dr ✓ 2/3Rr

Lem. 6.1

✓

Dr+1 ≤ 4/5Dr [22]

Rr+1 ≤

√ 15/4Rr

Lem. 6.5

✓ ✓

Table 2: Comparison of asynchronous multidimensional approximate-agreement algorithms. For our algorithms, α = 1. Here Rr denotes the radius of the minimum enclosing ball of the correct (m) values, Dr denotes their Euclidean diameter, and ∆r denotes the coordinate-wise working range in coordinate m. The contraction entries use different progress measures: Mendes–Herlihy contracts one coordinate range at a time, MidExtremes and MDA contract diameter, and our algorithms contract the MEB radius. The last column indicates whether the algorithm is coordinate-free. The inflated variant applies beyond the dimension-dependent resilience limitation of convex validity, for n > 4t. In the asynchronous model, messages can be delayed arbitrarily and a process cannot wait for all correct values to arrive. Hence, a process obtains a local view through the Gather protocol [2, 16], which guarantees a common-core of at least n − t values shared by all correct processes. However, the Gather protocol does not reveal which of the received values form the common-core. MEB validity for approximate agreement. The MEB-validity was introduced for vector consensus in [15]. Extending the definition into the approximate agreement poses new challenges. For the vector consensus, a process decides once and the validity condition concerns that single decision. In the approximate agreement the correct values are updated in every round, however the validity condition is stated with respect to the minimum enclosing ball of the initial correct values. It is therefore not enough to show that each value is close to the correct MEB of the current round. This bound must hold with respect to the initial correct MEB, and it must hold in every round. We consider two cases, depending on whether the candidate balls, that is, the minimum enclosing balls of all subsets of n − t received values whose intersection forms the safe area, have a common point. For n > (d + 1)t they do, by Helly’s theorem, which allows us to apply the adaptive contraction directly. At optimal resilience n > 3t the balls do not necessarily intersect, and we restore the intersection by multiplicatively increasing their radii. The remainder of this overview explains how these two ingredients, adaptive contraction and ball inflation, fit together. An Adaptive MEB Contraction Algorithm. Agreement is reached by shrinking the region that contains all correct values. Since each process computes its next value locally from its own received values, different correct processes may output different points. The contraction argument must therefore show that these outputs are geometrically closer to each other at the end of the round than they were at the beginning. We measure this progress using the radius Rr of the minimum enclosing ball of the correct values in round r. The key reason contraction is possible is that the local MEB-safe areas share a common point: every correct output is forced to stay close to this point, and this gives a common reference around which the new correct values can be enclosed. 4

Adaptive MEB Contraction Algorithm applies the core-set idea of Bădoiu and Clarkson [6, 7] (r) to the MEB-safe area: a process repeatedly adds the point of SafeMEBi farthest from the current minimax center, until every point of the safe area lies within αri of that center. As shown in Lemma 4.1, the √ parameter α trades √ computational effort against accuracy and p provides a contraction factor of α/ 1 + α2 , which is 1/ 2 ≈ 0.707 at α = 1 and improves on the 7/8 ≈ 0.935 of MidExtremes [24]. Note that the contraction bound does not depend on the dimension. The contraction proof is geometric. The selected points lie inside the correct MEB, which restricts the possible position of their minimax center ci . At the same time, the stopping condition ensures that the common point pr contained in all local MEB-safe areas is also close to ci . Combining these constraints gives a quadratic inequality involving the output, the current correct center Cr and the common point pr . Rewriting this inequality shows that every correct output lies in a ball centered at a weighted midpoint of Cr and pr , denoted by ar . Since this midpoint is common to all correct processes, the local inequalities imply a global bound on the next correct radius Rr+1 . Validity is not implied by contraction. Note that the radius contraction alone does not imply validity. That is because the center of the correct MEB may drift from round to round, so the contraction cannot keep the correct values close to the initial ball B(C0 , R0 ), centered at C0 with radius R0 . A naive proof for bounding the drift would sum these center movements over all rounds, but this would give weaker validity constant. We instead, in Theorem 5.1, establish the inequality for any two consecutive rounds: ∥Cr+1 − Cr ∥ + γRr+1 ≤ γRr , which states that the balls with enlarged radius by γ > 1 are nested, B(Cr+1 , γRr+1 ) ⊆ B(Cr , γRr ). Radius contraction then compensates for center drift within a single inequality, and induction gives H (r) ⊆ B(C0 , γR0 ) for all rounds, where H (r) denotes the set of correct values in round r. This is exactly γ-MEB validity with respect to the initial correct values. A similar argument applies to all four settings. Ball inflation. The previous contraction argument requires the candidate MEB balls defining the safe areas to have a common intersection. Above the Helly threshold, i.e. n > (d + 1)t, the intersection follows from Helly’s theorem. At optimal resilience n > 3t, however the balls do not necessarily intersect. We therefore in Theorem 5.3 prove a multiplicative inflation theorem for Euclidean balls. The theorem states: if every β balls of a finite family have a common point, then p inflating every radius by β/(β − 1) makes the entire family intersect. The factor is dimension-free. A countingpargument gives β ≥ 3 for n > 3t in the synchronous setting, so the required inflation is at most 3/2. The inflated algorithm then uses the but on the inflated safe √ same contraction, √ 2 to λα/ 1 + α2 . For α = 1 it gives area. This weakens the contraction factor from α/ 1 + α √ √ contraction factor at most 3/2 and 6-MEB validity. Thus, inflation gives dimension-free and optimal resilience n > 3t, at the price of slower contraction and a slightly larger validity constant. The proof of the inflation theorem is a dimension-free Helly-type argument in the spirit of Adiprasito, Bárány, Mustafa and Terpai [3] but the guarantee we need is different. Their theorem is additive, whereas c-MEB validity is multiplicative and requires bounds of the form ∥y − C ∗ ∥ ≤ cR∗ . We therefore need a guarantee relative to each ball’s own radius. Let λ∗ be the smallest inflation factor for which all balls intersect, and consider the balls that are tight at a witness point. The directions from this witness point to the centers of the tight balls must balance; otherwise the witness point could be moved slightly to decrease λ∗ . This balance may involve many balls, while the assumption only gives intersections for β balls at a time. The key step is to average over all β-tuples of tight directions and show that there are β of them that are already approximately balanced, with average direction of squared norm at most 1/β. Solving the inequalities we obtain p the bound λ∗ ≤ β/(β − 1). 5

Relating the safe area to the correct MEB. Our contraction analysis requires the local MEB-safe area to be contained in the correct MEB. When n > (d + 1)t, this holds trivially. The correct MEB is defined by at most d + 1 points, so there exists a locally computed candidate subset of size n − t containing the same d + 1 points. However, this argument does not hold for n > 3t. We repair it by intersecting over all subsets of size at least n − t, rather than exactly size n − t. Since the set of correct values H (r) is then itself a candidate subset, the inflated correct ball B(Cr , λRr ) appears in the intersection, and the local safe area is contained in it without any dependence on d. The asynchronous setting. In the asynchronous setting, using the Gather protocol a correct process may proceed without having received all correct values. Then, the MEB safe area cannot be compared to MEB(H (r) ) directly. Instead, we first compare it to the MEB of the correct values the process received and relate that local ball to the correct one in the second step. This additional comparison weakens the quadratic inequality used p in the synchronous proof. Consequently, the non-inflated asynchronous algorithm contracts by 2/3 for α = 1 at resilience n > (d + 2)t, whereas the inflated asynchronous algorithm works at dimension-free resilience n > 4t with contraction √ √ factor 15/4 and 2 10-MEB validity. Comparison with MDA. Minimum-Diameter Averaging is analyzed in terms of diameter contraction and is known to satisfy neither box nor convex validity [12]. Thus, the literature does not provide a directly comparable MEB-validity guarantee. In Lemma 7.2, we derive the MEBvalidity bound implied by its diameter contraction. This gives 7-MEB validity in the synchronous model and √ 11-MEB validity in the asynchronous model. √ By comparison, our inflated algorithms achieve 6 ≈ 2.45-MEB validity synchronously and 2 10 ≈ 6.32-MEB validity asynchronously, both under strictly better resilience thresholds.

1.3

Roadmap

We discuss related work in Section 2. In Section 3, we define the communication model, approximate agreement and MEB validity. Section 4 introduces Adaptive MEB Contraction and proves its contraction guarantee. In Section 5, we apply this algorithm in the synchronous setting, first above the Helly’s threshold and then at optimal resilience using ball inflation. Section 6 extends the approach to the asynchronous setting using the Gather protocol. Finally, Section 7 compares our guarantees with prior algorithms and discusses limitations and future work.

Related Work

Approximate agreement. Approximate agreement was introduced by Dolev et al. [21] as a relaxation of exact agreement in which correct processes do not agree on identical values, but on values that are sufficiently close to each other. Multidimensional approximate agreement generalizes this problem to inputs in Rd and was studied by Mendes, Herlihy, Vaidya and Garg [34, 35, 41]. The standard validity notion in this setting is convex validity, which requires every correct output to lie in the convex hull of the correct input vectors. However, convex validity leads to resilience thresholds dependent on dimension d. In particular, the established optimal resilience thresholds are n > (d + 1)t in the synchronous and n > (d + 2)t in the asynchronous setting [34, 35, 41]. An overview of applications of convex validity in other network models can be found in [25–27].

Validity conditions and relaxations. Validity conditions for Byzantine agreement and approximate agreement have been studied extensively. For binary and multi-valued exact agreement, common notions include strong validity, weak validity and correct-proposal validity [9,10,19,23,36,37]. For approximate agreement, convex validity is the standard geometric condition, however alternative one-dimensional validity notions, such as median validity and interval validity, have also been considered [17, 33, 39]. In the multidimensional setting, several works consider relaxed convex validity. Xiang et al. [43] study relaxed vector consensus, including lower-dimensional projections and (δ, p)-relaxed validity. Coordinate-wise relaxations lead to box validity notions, which can avoid the full convex validity barrier but are inherently tied to the choice of coordinates [12, 33]. In contrast, our work uses minimum enclosing balls, which ensure that the distance from the center of the correct minimum enclosing ball and the outputs is bounded by a constant factor of the radius. Minimum enclosing balls and MEB validity. The MEB-validity and the corresponding MEBsafe area were introduced for vector consensus by Cambus et al. [15]. Their work proposes MEB validity as a validity notion for vector consensus. Our work adapts MEB validity to approximate agreement. This poses a new challenge, as the agreement is iterative, the validity must be preserved over all rounds. Concurrent work by Melnyk [32] also uses minimum enclosing balls in its contraction algorithm, but applies them to the convex safe area under convex validity. Ball validity is also motivated by practical approximate agreement, such as Minimum-Diameter Averaging (MDA) that selects a subset of small diameter and averages it [22]. Core-sets and algorithms for minimum enclosing balls. Our Adaptive MEB Contraction algorithm is inspired by the core-set construction of Bădoiu and Clarkson [6, 7]. Their algorithms approximate the minimum enclosing ball of a finite point set by repeatedly adding farthest points to a small core-set. We use the same idea, however the farthest point is chosen from a continuous MEB-safe area rather than from a finite input set. Additional related work on approximate minimum enclosing encompasses similar core-set constructions [29] and gradient-type methods [28]. Communication primitives. Byzantine agreement protocols rely on broadcast routines which ensure the delivery of the messages. In the synchronous setting, we use consistent broadcast [11,31,38], closely related to Crusader Agreement [38], which guarantees consistency among values delivered by correct processes. However, unlike reliable broadcast [10], it does not require all correct processes to deliver a value from a faulty sender. The term consistent broadcast was later used by Cachin et al. [11]; see also [4, 5] for a discussion of the broadcast routines. In the asynchronous setting, we use the Gather protocol originating with Canetti–Rabin [16] and later extended by Abraham et al. [1, 2].

Model

Correct and faulty processes. We consider a distributed system consisting of n processes 1, 2, . . . n, of which at most t are faulty. Correct processes follow the protocol, while faulty processes are corrupted throughout the entire execution. Faulty processes, also referred to as Byzantine, know the input vectors of all other processes, as well as the agreement algorithm, and they are allowed to collaborate. Byzantine processes may send arbitrary values or omit messages, however their behavior is imposed by the communication model described below. Note that the correct processes cannot identify which processes are faulty or how many faulty processes there are; they only know the upper bound t on the number of Byzantine processes.

Throughout the paper, we consider the multidimensional setting d ≥ 2. Each process i starts (0) with an initial input value mi ∈ Rd . In each round r, process i maintains a single current value (r) mi ∈ Rd , which depends on the initial input value and the information received and processed during the execution of the algorithm. In particular, each process combines the received information into a single value, which becomes its current value for the next round. If the current round is insignificant, we will omit r from the variables and simply write mi . We use H to denote the set (r) of correct, non-faulty processes and H (r) = {mi | i ∈ H} to denote the current values of correct processes in round r. Note that |H| ≥ n − t. Communication. In this work, we consider both synchronous and asynchronous settings with non-authenticated channels, as it is commonly studied in the literature [20,21,36]. In the synchronous setting, computation proceeds in rounds. In each round, every correct process consistently broadcasts its current value. Consistent broadcast [11, 31, 38] guarantees that every correct process receives the value broadcast by each correct process. Moreover, if two processes receive a value from the same sender, then it must be the same value. Note that a Byzantine process may send its value to some correct processes and not to others. We refer to the set of values received by a process in a round as (r) (r) its local view. We denote the local view of correct process i in round r by Pi . Thus, H (r) ⊆ Pi . In the asynchronous setting, we use a primitive [2, 16] to obtain local views. When a correct (r) process i invokes Gather in round r, it obtains a local view Pi containing values associated with their respective senders. The Gather protocol satisfies the following properties: • Common-core: There exists a set denoted by GTHR(r) of values from at least n − t distinct (r) senders, such that GTHR(r) ⊆ Pi for every correct process i. (r)

• Validity: If a value associated with a correct sender j is contained in Pi , then this value is (r) j’s current value mj in round r. • Agreement: If two correct parties include values associated with the same sender j in their local views, then these values are identical. Note that, the set GTHR(r) is common to all correct processes, although the processes do not necessarily know which values belong to GTHR(r) . Multidimensional approximate agreement. In this work, we consider multidimensional approximate agreement algorithms, where the approximation is defined with respect to the Euclidean distances: Definition 3.1 q (Euclidean Distance). For any v, v ′ ∈ Rd , the Euclidean distance between v and

d ′ 2 v ′ is ∥v − v ′ ∥ = i=1 (vi − vi ) , where vi is the projection of v on coordinate i ∈ [d]. We write P ⟨v, v ′ ⟩ = di=1 vi vi′ for the Euclidean inner product, so that ∥v∥2 = ⟨v, v⟩.

Approximate agreement algorithms allow processes to agree on a vector, even in presence of Byzantine processes. An algorithm that solves multidimensional approximate agreement must satisfy the following properties: • Agreement: The output vectors of all correct processes must be within a distance ε > 0 from (r) (r) each other, i.e. ∥mi − mj ∥ ≤ ε for i, j ∈ H. • Validity: The outputs of all correct processes satisfy the specific validity condition defined with respect to the initial inputs of the correct processes.

• Termination: Each correct process must terminate in finite time, i.e. decide on a final output value and stop participating in the protocol. The standard validity notion used in multidimensional approximate agreement is convex validity. Definition 3.2 (Convex Validity). An algorithm satisfying convex validity must output a vector inside the convex hull of correct processes. Mendes et al. [35] provide a multidimensional approximate agreement algorithm based on the Safe Area computation. In the algorithm, each correct process i computes the intersection of all convex hulls on subsets of size n − t. This intersection is referred to as the Safe Area. Moreover, in [35], the authors show that satisfying convex validity requires agreeing inside the Safe Area. In order for the Safe Area to exist, the resilience must be t < n/(max{3, d + 1}). However, this requirement implies that the algorithm cannot be used in the case when n ≤ d. Therefore, we use a relaxation of the convex validity, which allows dimension-free resilience. MEB validity. We propose minimum enclosing ball MEB validity and its multiplicative relaxation, c-MEB validity, where c is a constant, first introduced for the vector consensus setting in [15]. MEB validity relies on allowing processes to agree inside the minimum enclosing ball of correct inputs. In the following, we formally define the MEB and c-relaxed MEB validity conditions. Definition 3.3 (MEB validity). MEB validity condition requires that the output vector of each non-faulty process must lie inside the minimum enclosing ball of the input vectors of all non-faulty processes denoted by correct MEB. As authors in [15] state, the MEB is unique, so MEB validity is well defined. Note that the diameter between two correct vectors is not necessarily unique. Moreover, the minimum enclosing ball of correct inputs is convex and contains all of them, hence it contains their convex hull, so convex validity implies 1-MEB validity. However, Cambus et al. [15] show that exact MEB validity suffers from resilience limitations, similar to convex validity. Hence, we relax the MEB validity by increasing the radius of the MEB of correct processes by a factor and improve the resilience. Definition 3.4 (c-MEB validity). Let H be the set of input vectors of correct processes, and let MEB denote their minimum enclosing ball with center in C ∗ and radius R∗ . An algorithm satisfies c-MEB validity if every non-faulty process outputs a vector y such that ∥y − C ∗ ∥ ≤ c · R∗ . Note that, if c = 1 this condition is the exact MEB validity. Throughout the work, we will name this the c-relaxed MEB validity condition. In order to satisfy MEB validity, it is necessary to agree inside the intersection of MEB of all possible n − t subsets of vectors, as shown in [15]. This area is defined analogously to the safe area for convex validity [41]: Definition 3.5 (MEB-safe area [15]). Let S be a set of vectors in Rd , with |S| ≥ n − t. Then, the safe area for MEB validity, denoted SafeMEB, is defined as: SafeMEB =

MEB(T ).

T ⊆S,|T |=n−t (r)

In round r, the local MEB-safe area computed by process i is SafeMEBi

(r)

T ⊆Pi |T |=n−t

MEB(T ).

For c-MEB validity, we define the c-SafeMEB area analogously, by replacing each minimum enclosing ball MEB(T ) = B(CT , RT ) in the intersection with the inflated ball B(CT , c · RT ). 9

Adaptive MEB Contraction

In this section, we introduce the Adaptive MEB Contraction for solving multidimensional approximate agreement with MEB-validity. First, each process locally computes the MEB-safe area (r) SafeMEBi as an intersection of smallest enclosing balls on all subsets of size n − t. For now, we assume that n > (d + 1)t, so that such intersection of the balls always exists. Later we will generalize this algorithm to work on n > 3t and in the asynchronous setting. The Adaptive MEB Contraction is inspired by the core-set construction of Bădoiu and Clarkson [6, 7], which iteratively adds a point which is farthest from the center of its current minimum enclosing (r) ball. In contrast, we apply a similar principle to the MEB-safe area SafeMEBi and terminate once (r) all points of SafeMEBi are within a predefined distance from the center. (r) Initially, each process i computes the MEB-safe area SafeMEBi and adds the two diameter (r) points of SafeMEBi to the selected set Si . Then the algorithm computes the center ci that minimizes the maximum distance to the selected points from set Si . Next, the algorithm chooses the point qi , which is the farthest away from the current minimax center ci . Then, we check how well the (r) current center ci represents the MEB-safe area SafeMEBi : if the point qi is within distance α · ri , (r) where ri is the maximum distance from ci to the points in set Si , then all points of SafeMEBi are within distance α · ri . This way, the stopping criteria is satisfied, so the algorithm outputs ci . Otherwise, the point qi is added to the selected set Si and the process repeats. The selected set Si collects points of the MEB-safe area that are most relevant for determining a center that represents the entire area. The algorithm is adaptive because it keeps adding such points (r) only until the current center approximates all of SafeMEBi within the factor α. The pseudocode of the Adaptive MEB Contraction is presented in Algorithm 1. Figure 1 illustrates one iteration of the Adaptive MEB Contraction algorithm. Algorithm 1 Adaptive MEB Contraction (for process i) √ (r) Require: Input value mi , threshold 1 ≤ α ≤ 3 (see Remark 4.3) (r+1) Ensure: New input value mi (r) (r) 1: consistently broadcast mi and receive set Pi T (r) 2: Compute the MEB-safe area SafeMEBi = (r) MEB(T ) T ⊆P i

3: Choose two diameter points: ai , bi ∈ arg max 4: Initialize the selected set Si ← ai , bi

|T |=n−t (r)

x,y∈SafeMEBi

∥x − y∥

5: repeat 6: 7: 8:

Compute the minimax center of the selected set: ci ∈ arg minc∈Rd maxs∈Si ∥s − c∥ Define the corresponding radius: ri = maxs∈Si ∥s − ci ∥ Find a farthest point from the current center: qi ∈ arg maxx∈SafeMEB(r) ∥x − ci ∥

if ∥qi − ci ∥ ≤ αri then (r+1) 10: return mi ← ci 11: else 12: Add this point: Si ← Si ∪ {qi } 13: end if (r) 14: until all points of SafeMEBi within radius αri

The parameter α controls how far away the points are allowed to lie from ci . For a larger α > 1, 10

Initialization

Add farthest point

Updated center

∥q − c0 ∥ =

√

3 > r0 r1

add q

c1 c0 a

c0 b

S = {a, b} c0 = (0, 0), r0 = 1

b √

S ← S ∪ {q}

√

c1 = (0, 33 ), r1 = 2 3 3 stopping criterion satisfied

Figure 1: One iteration of the Adaptive MEB Contraction Algorithm with α = 1. The blue region is the local MEB-safe area computed in Line 2, here the intersection of three balls of radius 2 centered √ at (−1, 0), (1, 0) and (0, 3). The two diameter points a = (−1, 0) and b = (1, 0) give c0 = (0, √0) and r0 = 1, and the dashed circle√ is ball centered at c0 with radius r0 . The farthest point q = (0, 3) of the safe area lies at distance 3 > r0 from c0 , so the stopping√criterion fails √and q is added to the selected set. Recomputing the minimax center gives c1 = (0, 33 ) and r1 = 2 3 3 ; the whole safe area is now contained in B(c1 , r1 ), so the algorithm outputs c1 . the algorithm may stop after only a few selected points in set Si . For α = 1, the algorithm stops (r) (r) only if the entire MEB-safe area SafeMEBi is at distance ri from ci , i.e. SafeMEBi ⊆ B(ci , ri ) = (r) MEB(SafeMEBi ). Thus, for α = 1, the output ci is exactly the center of the minimum enclosing ball of the entire MEB-safe area. Equivalently, the α = 1 update may be implemented by computing (r) the center of MEB(SafeMEBi ). This case is also closely related to the approach in [32], which computes the minimum enclosing ball of the convex safe area instead. Intermediate values of α interpolate between the two cases. The Adaptive MEB Contraction can thus also be seen as an extension of the MidExtremes algorithm [24] used on the MEB-safe area. MidExtremes considers only the two initial diameter points in Si and directly outputs their midpoint. In contrast, our algorithm adds further points until the current midpoint satisfies the predefined α · ri threshold. Next, we analyze the contraction factor of Adaptive MEB Contraction, which determines how α quickly the correct values converge. We show that the contraction factor is Rr+1 ≤ √1+α Rr . Note 2 that the contraction factor of our algorithm does not depend on the dimension d. Lemma 4.1. In the synchronous setting with n > (d + 1)t, √ the contraction rate of Adaptive MEB α Contraction Algorithm is Rr+1 ≤ √1+α R , for 1 ≤ α ≤ 3. r 2 Proof. Let H (r) denote the value of correct processes in round r, and MEB(H (r) ) = B(Cr , Rr ) be the smallest enclosing ball around H (r) with center Cr and radius Rr . Moreover, let Rr+1 denote the radius of the new correct values after all correct processes output their ci . In Adaptive MEB (r) Contraction Algorithm every process i computes the MEB-safe area SafeMEBi . Per definition, (r) every locally computed safe area is inside the correct MEB(H ), with center Cr and radius Rr . Next, since n > (d + 1)t, all locally computed MEB-safe areas intersect. Indeed, consider any d + 1 candidate balls used in the construction of the MEB-safe areas, defined by sets T1 , . . . , Td+1 of size n − t. Each set Tj omits at most t processes, and therefore the d + 1 sets omit at most (d + 1)t < n processes in total. Hence, there exists a process contained in all sets Tj . By consistent broadcast, this process contributes the same value to all corresponding sets, and this value lies in all d + 1 11

candidate balls. Thus, every d + 1 candidate balls intersect, and by Helly’s theorem [18] the whole family of candidate balls has a nonempty intersection. Consequently, all locally computed MEB-safe (r) areas intersect, so there exists a point pr such that pr ∈ SafeMEBi for every correct process i. (r) Each process i maintains a selected set of points Si in SafeMEBi and computes the point that minimizes the largest distance to the selected points denoted by ci . Since all selected points are within distance ri from ci , then the set Si is inside the ball centered at ci with radius ri , (r) i.e. Si ⊆ B(ci , ri ). Because Si ⊆ SafeMEBi , set Si is also inside the correct MEB(H (r) ), i.e. Si ⊆ B(Cr , Rr ). Since B(ci , ri ) is the smallest ball which contains Si , and since Si is also contained in B(Cr , Rr ), we get: ∥ci − Cr ∥2 + ri2 ≤ Rr2 .

(1)

We refer to this property as the MEB containment inequality. This implies that if the radius ri is large, then the center ci must be close to the center Cr . If additionally ci was also far from Cr , then the selected set Si could not be inside B(Cr , Rr ). (r) Next, Adaptive MEB Contraction Algorithm finds a point qi ∈ SafeMEBi which is farthest (r) away from the center ci and stops if ∥qi − ci ∥ ≤ αri . Then, every other point from SafeMEBi has a smaller distance to ci than qi . This also holds for the common point pr , so ∥pr − ci ∥ ≤ αri . Rewriting this gives: ri2 ≥

1 ∥pr − ci ∥2 . α2

(2)

We plug Inequality 2 into Inequality 1 and get: ∥ci − Cr ∥2 +

1 ∥ci − pr ∥2 ≤ Rr2 . α2

(3)

This inequality implies that the output ci of Adaptive MEB Contraction Algorithm cannot be too far from both center of the MEB Cr and common point pr . Next, we rewrite this as squared distance from ci to the point ar , which is the weighted midpoint between Cr and pr , i.e. ar =

Cr + 12 pr α

1+ 12

. Thus,

∥ci − Cr ∥2 +

1 1 1 ∥ci − pr ∥2 = 2 ∥Cr − pr ∥2 + (1 + 2 )∥ci − ar ∥2 ≤ Rr2 . 2 α α +1 α

(4)

From this inequality, we can conclude that (1 + α12 )∥ci − ar ∥2 ≤ Rr2 . Hence, ∥ci − ar ∥ ≤ √

α Rr . α2 + 1

(5)

α So, every correct output ci of Adaptive MEB Contraction Algorithm lies inside the ball B(ar , √1+α Rr ), 2 α √ centered in point ar with radius 1+α2 Rr . Therefore, the minimum enclosing ball of the new correct α Rr . This concludes the proof. values cannot have a larger radius than this ball, i.e. Rr+1 ≤ √1+α 2

√ α We proved that the contraction rate of Adaptive MEB Contraction is √1+α , where 1 ≤ α ≤ 3. 2 The parameter α controls the tradeoff between computational effort and contraction. Smaller values of α require the selected support set Si to represent the MEB-safe area more accurately and therefore provide a stronger contraction. 12

Corollary 4.2. For α = 1 the Adaptive MEB Contraction Algorithm has contraction rate √12 ≈ 0.707. This bound is dimension-independent and is substantially smaller than the 7/8 ≈ 0.935 contraction bound shown for MidExtremes [24]. In Section 7, we give an example for α = 1 in which the contraction factor is exactly √12 , showing that our analysis is tight. p

Remark 4.3. Note that α does not need to be upper bounded, however we show that by taking only the initial two diameter points of the MEB-safe area into the selected set Si , Adaptive MEB √ Contraction Algorithm already satisfies the stopping criterion for α = 3. (r)

Lemma 4.4. Let Si be initialized with the two diameter points of the MEB-safe region SafeMEB i . √ Then Adaptive MEB Contraction Algorithm already satisfies the stopping criteria for α = 3 after this initialization. (r)

i i Proof. Let ai , bi be the two diameter points of SafeMEBi . Then, ci = ai +b and ri = Diam 2 2 , where Diami is the distance between ai and bi . This is equivalent to the MidExtremes Algorithm [24] (r) (r) computed on the MEB-safe area SafeMEBi . Then, every point x of SafeMEBi is at distance i smaller than αDiam from ci . Using the parallelogram law, we obtain ∥x − ai ∥2 + ∥x − bi ∥2 = 2∥x − 2

Diam2i Diam2 . Since ∥x − ai ∥ ≤ Diami and ∥x − bi ∥ ≤ Diami , we get 2∥x − ci ∥2 + 2 i ≤ 2Diam2i . 2 √ (r) Rearranging the terms gives ∥x − ci ∥ ≤ 3 · ri , implying that all points of SafeMEBi are at distance √

ci ∥2 +

3 · ri from ci . Hence, the stopping criteria in Adaptive MEB Contraction Algorithm is directly √ satisfied for α = 3. This√implies that taking the MidExtremes point of the MEB-safe area provides contraction p rate of 23 ≈ 0.866. This improves over the contraction factor 7/8 ≈ 0.94 proved for the classical MidExtremes algorithm in [24], although the two bounds are obtained in different models.

Synchronous Multidimensional Approximate Agreement

In this section, we apply Adaptive MEB Contraction in the synchronous setting. First, we consider the setting with n > (d + 1)t in Section 5.1, in which all candidate balls for the MEB-safe area intersect. Then, we focus on the optimal resilience case n > 3t, where the intersection of the balls is not guaranteed. Hence, we show in Section 5.2 that we can inflate the candidate balls by a factor and obtain a common intersection. Then, in Section 5.3, we show that using the Adaptive MEB Contraction Algorithm on inflated candidate balls solves multidimensional approximate agreement with optimal resilience n > 3t.

5.1

Resilience n > (d + 1)t

In the following, we show Adaptive MEB Contraction Algorithm solves multidimensional approximate agreement when n > (d + 1)t. In this scenario, all locally computed MEB-safe areas intersect, as shown in Lemma 4.1. Theorem 5.1. Assume the synchronous setting with n > (d + 1)t. MEB Contraction Al Adaptive gorithm solves multidimensional approximate agreement after O √ 1 + α2 -MEB validity.

log(R √ max /ε) log( 1+α2 /α)

rounds and satisfies

Proof. We first show the convergence. As shown in Lemma 4.1, the contraction rate of Adaptive MEB α Rr , where Rr denotes the radius of the minimum enclosing Contraction Algorithm is Rr+1 ≤ √1+α 2

α α R0 ≤ √1+α Rmax , ball around correct processes in round r. After r rounds, Rr ≤ √1+α 2 2 where Rmax is the known upper bound on the initial correct MEB radius. Since every correct (r) ) = B(C , R ), the distance between any two correct values is at most value lies in MEB(H r r r α R ≤ ε and Adaptive MEB Contraction Algorithm converges after 2Rr ≤ ε. Hence, 2 √1+α max 2

' log(2R √max /ε) 2 log( 1+α ) α

rounds. Since Rmax is known to all correct processes, they can terminate after this

predetermined number of rounds. Thus, Adaptive MEB Contraction Algorithm satisfies ε-agreement and termination. √ Next, we show that Adaptive MEB Contraction Algorithm satisfies 1 + α2 -MEB validity. The main difficulty is that the contraction only controls the radius Rr . It does not prevent the center of MEB to drift away over multiple rounds. So, for validity, we want to show that all correct values in all rounds stay close to the initial correct MEB, i.e. H (r) ⊆ B(C0 , γR0 ) for each round r, where γ is the validity factor. In order to bound the drift, we show that ∥Cr+1 − Cr ∥ + γRr+1 ≤ γRr .

(6)

Intuitively, in every round the radius of the MEB decreases, while the center of the MEB of the next round might move. However, the radius contraction is strong enough to compensate for the movement. From the proof of Lemma 4.1, for every correct output ci , we have ∥ci − Cr ∥2 + α12 ∥ci − pr ∥2 ≤ Rr2 , where pr is a common point contained in every local MEB-safe area. Additionally, consider the point ar =

Cr + 12 pr α

1+ 12

defined in Lemma 4.1 and Inequality 4. Then,

∥ci − ar ∥2 ≤

Rr2 − α21+1 ∥Cr − pr ∥2 1 + α12

= σr2 .

(7)

This implies that every correct output ci lies in the ball B(ar , σr ), centered at ar with radius σr . Since all new correct values lie in B(ar , σr ) and their minimum enclosing ball is MEB(H (r+1) ) = 2 B(Cr+1 , Rr+1 ), the MEB containment inequality gives ∥Cr+1 − ar ∥2 + Rr+1 ≤ σr2 . We now bound the validity factor γ from Inequality 6. By triangle inequality, we get ∥Cr+1 − Cr ∥ + γRr+1 ≤ ∥ar − Cr ∥ + ∥Cr+1 − ar ∥ + γRr+1 . Plugging in the formula for ar into the first term and using Cauchy-Schwarz and substituting the definition of σr for the second and third term on the right side gives: ∥Cr+1 − Cr ∥ + γRr+1 ≤

1 α2 + 1

v u u Rr2 − α21+1 ∥Cr − pr ∥2 t 2 ∥Cr − pr ∥ + (1 + γ ) 1

1 + α2

v u u 1 + γ 2 + 12 α ≤t R . r

1 + α12 s

1+γ 2 + 1

(8) (9)

α2 Hence, it is enough to choose a γ such that ≤ γ. After solving this inequality, the smallest 1+ 12 α √ √ √ possible choice of γ is γ = 1 + α2 , so we obtain ∥Cr+1 − Cr ∥ + 1 + α2 Rr+1 ≤ 1 + α2 Rr . This holds for every two consecutive rounds r and r + 1.

In order to show validity, we must √ bound the drift √ of the center of the MEB from C0 . We now 2 prove by induction that ∥Cr − C0 ∥ + 1 + α Rr ≤ 1 + α2 R0 for every round r. For r = 0, the inequality holds. Now assume that it holds for some round r. Then, by the triangle inequality we get: ∥Cr+1 − C0 ∥ +

1 + α2 Rr+1 ≤ ∥Cr − C0 ∥ + ∥Cr+1 − Cr ∥ + ≤ ∥Cr − C0 ∥ + ≤

1 + α2 Rr

1 + α2 R0

1 + α2 Rr+1

(10) (11) (12)

This completes the induction. Hence, for every round r it holds that ∥Cr − C0 ∥ +

1 + α2 Rr ≤ 1 + α2 R0 . √ √ Since 1 + α2 ≥ 1, this also implies ∥Cr − C0 ∥ + Rr ≤ 1 + α2 R0 . Now, we can use this bound to show that the correct processes also stay close to the center of the initial MEB(H (0) ). Let x ∈ H (r) be any correct input in round r. Since MEB(H (r) ) = B(Cr , Rr ), we get ∥x − Cr ∥ ≤ Rr . Then by triangle inequality ∥x − C0 ∥ ≤ ∥x − Cr ∥ + ∥Cr − C0 ∥ ≤ Rr + ∥Cr − C0 ∥ ≤

1 + α2 R0 .

(13) (14) (15)

This inequality holds for every correct input and every√round r. This implies that every √ correct input stays inside the ball centered at C0 with radius√ 1 + α2 R0 , i.e. H (r) ⊆ B(C0 , 1 + α2 R0 ). Thus, Adaptive MEB Contraction Algorithm satisfies 1 + α2 -MEB validity. We showed that Adaptive MEB Contraction Algorithm solves multidimensional approximate √ 2 agreement in the synchronous setting with n > (d + 1)t while satisfying 1 + α -MEB validity. The following corollary highlights the resulting validity guarantees for particular choices of α. √ Corollary 5.2. For α = 3,√Adaptive MEB Contraction Algorithm satisfies 2-MEB validity, whereas for α = 1, it satisfies 2 ≈ 1.41-MEB validity. In particular, lower values of α obtain better MEB-validity guarantees. Note that in the proof of Lemma 4.1 we can bound validity by summing over all possible center movements over all rounds. Since the radius shrinks, this bounds the total drift based on geometric series, however it provides a weaker validity constant. Hence, we proved a stronger bound by considering the drift of centers and radius contraction simultaneously. We next focus on the optimal resilience synchronous setting n > 3t.

5.2

Ball Inflation Analysis

In this section, we apply the Adaptive MEB Contraction to solve the multidimensional approximate agreement algorithm satisfying MEB-validity with optimal resilience n > 3t. Note, when n > 3t, there is no guarantee that all candidate MEBs intersect and that the MEB-safe area is non-empty. Hence, in order to ensure the intersection, we increase each candidate MEB’s radius by a factor of λ ≥ 1 and show that all MEBs after q inflation have a common intersection point. First, we β upper bound the inflation factor λ ≤ β−1 . Then, we show that using Adaptive MEB Contraction 15

λα Algorithm, we solve multidimensional approximate agreement with contraction factor √1+α and 2

satisfy λ 1+α1+α 2 −λ2 α2 -MEB validity. In the following, we show that if any subset q of β balls have a non-empty intersection, then β increasing each ball’s radius by a factor 1 ≤ λ ≤ β−1 ensures that all balls intersect. A similar result is known for general convex sets [3], but only as an additive bound, whereas we need the multiplicative inflation factor relative to each candidate MEB’s own radius. Theorem 5.3. Let B = {B(CT , RT ) : T ∈ T } be a finite family of Euclidean balls in Rd . Suppose that every subfamily of at most β ≥ q2 balls has a nonempty intersection. Then, after increasing the β all balls have a common intersection point, i.e. radius of every ball by a factor of β−1 s \ T ∈T

B CT ,

β RT β−1

̸= ∅.

Proof. The proof consists of four main steps. (i) Let λ∗ be the smallest inflation factor for which the inflated balls have a common point x∗ . It p suffices to show λ∗ ≤ β/(β − 1), since any inflation factor which is at least λ∗ provides a common intersection of the balls. (ii) We call a ball active if x∗ lies on the boundary of the inflated ball and we call the unit vector pointing from x∗ towards the center of an inflated active ball its active direction. We show that the active directions are balanced and cancel out. Otherwise we could move x∗ in one direction and reduce λ∗ . (iii) The cancellation in (ii) may involve all active balls. However, the assumption only provides a nonempty intersection for every β balls at a time. By averaging over all β-tuples of active directions, we show that there are at most β such balls that p are approximately balanced, i.e. their average direction, instead of being zero, has norm at most 1/β. (iv) Since every subset of β balls has a common intersection point before inflation, the balls which are approximately balanced also have a common intersection point y. Then, y lies within Rj from each of theirpcenters, while x∗ lies at distance λ∗ Rj from the centers. Combining the two gives the bound λ∗ ≤ β/(β − 1). Step 1: The minimal inflation factor. Note that, if some ball has radius zero, then pairwise intersection implies that its center belongs to every ball. Hence, assume that RT > 0 for every T ∈T. ∥x−C ∥ Let λ∗ = minx∈Rd maxT ∈T Rj j , and let x∗ be a minimizer. Thus, λ∗ ≥ 1 is the smallest factor ∗ by which all balls must be enlarged to obtain a common p intersection ∗and x is the point contained ∗ ∗ in all balls inflated by λ . It suffices to prove λ ≤ β/(β − 1). If λ ≤ 1 the claim is immediate, so assume λ∗ > 1. Without the loss of generality, translate the coordinate system such that x∗ = 0. Step 2: The active balls are balanced. Let A = {T ∈ T : ∥CT ∥ = λ∗ RT } be the set of active balls, for which the first intersection point lies on the boundary of the inflated ball. We refer to a ball as inactive, if ∥CT ∥ < λ∗ RT . We claim that 0 ∈ conv

CT 2 RT

: T ∈ A . Suppose not. Then, by

the separating hyperplane theorem [42], there exists a vector h such that

CT h, R 2 T

> 0 for every

T ∈ A. Let fT (x) = ∥x − CT ∥2 /RT2 and consider moving from x∗ = 0 to εh for ε > 0. Expanding

this term gives

∥CT ∥2 CT ∥εh − CT ∥2 = − 2ε h, 2 fT (εh) = 2 RT RT2 RT

+ ε2

∥h∥2 . RT2

For T ∈ A the first term is equal to (λ∗ )2 and the second term is strictly negative, which implies that fT (εh) < (λ∗ )2 for all sufficiently small ε > 0. Additionally, every inactive ball satisfies fT (0) < (λ∗ )2 . Since fT is continuous and the inequality at x∗ is strict for inactive balls, fT (εh) also stays below (λ∗ )2 for all sufficiently small ε. For each ball individually, the above holds once ε is small enough, but the threshold depends on the ball. Since T is finite, we can take the smallest of these thresholds, which is still positive. For such an ε, every ball satisfies ∥εh − CT ∥ < λ∗ RT , so the point εh lies in all balls inflated by a factor strictly below λ∗ , contradicting the minimality of λ∗ . This shows that x∗ could be moved slightly in that direction and decrease the distances P of all active balls. Therefore, there exist coefficients aT ≥ 0, T ∈ A, such that T ∈A aT = 1 and P CT T ∈A aT R2 = 0, meaning that the directions of all active balls cancel out. T

T For T ∈ A, define the unit direction uT = λC ∗ R . Since T is an active ball, ∥uT ∥ = 1. Substituting T P CT CT = λ∗ RT uT into the balance condition T ∈A aT R 2 = 0 gives T

T ∈A

X λ∗ uT uT = λ∗ aT = 0. RT R T T ∈A

Since λ∗ > 1, we obtain T ∈A RaTT uT = 0. After normalizing the coefficients aT /RT , we obtain P P weights pT ≥ 0 satisfying T ∈A pT = 1 and T ∈A pT uT = 0. P

Step 3: Choosing at most β balanced directions In Step 2 we showed that the directions of active balls cancel out exactly, but the cancellation involves the entire set A. Our assumption is however that every β balls have a common intersection point, so we can only exploit the option of β balls canceling out. We therefore trade exact cancellation over many directions for approximate cancellation over few, and show that some β of the active directions already approximately cancel. Consider all ordered β-tuples consisting of elements of the set of active balls T = (T1 , . . . , Tβ ) ∈ Q β A . Assign to each tuple the weight wT = βj=1 pTj . These weights are nonnegative and summing the product over all tuples gives the product of β sums of pT over A, each of which is 1 by Step 2. P P Hence, T ∈Aβ wT = ( T ∈A pT )β = 1. For each tuple, consider the squared norm of its average direction. We compute the weighted 2

average of these squared norms: D = T ∈Aβ wT β1 βj=1 uTj . Expanding the squared norm into inner products, D splits into β diagonal terms, one for each position j, and β(β − 1) cross terms, one for each ordered pair of distinct positions j and k, all divided by β 2 :   P

X X X X  1  2  . w ⟨u , u ⟩ w ∥u ∥ + T T T T T j j k   β 2 j=1 β β j,k=1 T ∈A

T ∈A

j̸=k

For each position j, the corresponding diagonal term satisfies T ∈Aβ wT ∥uTj ∥2 = T ∈A pT ∥uT ∥2 = 1, because uT is a unit vector. There are β such terms, so together they contribute to ββ2 = β1 . Moreover, the cross terms all vanish. Fix j ̸= k. Since uTj and uTk do not involve the remaining P β − 2 positions, summing those out gives T ∈A pT = 1. This leaves the double sum over j and k, P P P which equals 0 by Step 2: T ∈Aβ wT ⟨uTj , uTk ⟩ = ⟨ T ∈A pT uT , T ′ ∈A p′T u′T ⟩ = 0. P

Consequently, D = ββ2 = β1 . Since D is a weighted average with nonnegative weights summing to one, at least one tuple exists with a value not larger than the average. Fix such a tuple (T1 , . . . , Tβ ) ∈ Aβ , so that the squared norm of its average direction is at most 1/β. Note that its indices are not necessarily distinct. So, it remains to remove the repetitions from this tuple. Let J ⊆ A be the set of distinct indices. Since the tuple has β entries, then |J| ≤ β. For each T ∈ J, let θT be the fraction of β positions P in which T occurs. Then θT ≥ 0, T ∈J θT = 1, and defining z as the sum of θT uT over T ∈ J, i.e. P z = T ∈J θT uT gives exactly the average direction of the tuple: ∥z∥2 ≤ β1 . We have thus found at most β active balls whose directions are balanced up to 1/β. Step 4: Bounding the inflation factor via common point Now we have two pieces of information about the balls in J. On the one hand, they are at most β many, so by assumption they have a common point y before inflation: their centers all lie within their own radii of a single location. On the other hand, they are active, so their centers lie at distance exactly λ∗ RT from x∗ and by Step 3 they are spread around x∗ in nearly balanced directions. To compare the two, we estimate P the weighted average squared distance from y to the selected centers, i.e. T ∈J µT ∥y − CT ∥2 . T Fix y ∈ T ∈J B(CT , RT ) as a common point of balls from set J before inflation. Thus, ∥y − CT ∥ ≤ RT for every T ∈ J. P Note that the balls in J can have different radii. In order to normalize this, we set P = T ∈J RθTT T and Q = T ∈J θT RT , and define the weights µT = θT /R . The coefficients µT are nonnegative and P P P ∗ T sum to one. This way, reweighting by 1/RT gives exactly T ∈J µT CT = T ∈J θT /R λ∗ RT uT = λP z , P where z is the average direction computed in Step 3. P Next we upper bound the term T ∈J µT ∥y − CT ∥2 . Since y ∈ B(CT , RT ) for every T ∈ J,

µT ∥y − CT ∥2 ≤

T ∈J

µT RT2 =

X T ∈J

Next, we focus on the lower bound on

Q . P

(16)

2 T ∈J µT ∥y − CT ∥ . Expanding the square gives:

µT ∥y − CT ∥ = y − 2

µT C T

µT ∥CT ∥ −

µT CT

T ∈J

≥

µT ∥CT ∥ −

µT C T

T ∈J

Since CT = λ∗ RT uT for every T ∈ J, then we obtain P ∗ P ∗ and T ∈J µT CT = λP T ∈J θT uT = λP z for the second. Combining this with Inequality (16) gives

2 ∗ 2Q T ∈J µT ∥CT ∥ = (λ ) P for the first term

∗ 2

(λ )

Q ∥z∥2 − 2 P P

≤

µT ∥y − CT ∥2 ≤

T ∈J

Q . P

Since Q/P > 0, this is equivalent to: ∗ 2

(λ )

∥z∥2 1− PQ

≤ 1.

(17)

Using Cauchy–Schwarz on P Q, we obtain PQ =

X θT T ∈J

! X

θT RT

≥

T ∈J

θT

= 1.

T ∈J

1 2 Therefore, ∥z∥ P Q ≤ ∥z∥ ≤ β , and we can use this to simplify Inequality (17). Since β ≥ 2, it follows that 1 (λ∗ )2 1 − ≤ 1, β

and hence

s ∗

λ ≤ Thus, the balls enlarged by the factor

5.3

β . β−1

β β−1 have a common intersection.

Multidimensional Approximate Agreement with Optimal Resilience n > 3t

We now combine the ball-inflation theorem from Section 5.2 with Adaptive MEB Contraction. This gives a synchronous algorithm with dimension-free resilience n > 3t. Our approach is to run the Adaptive MEB Contraction Algorithm on inflated candidate balls. In particular, each correct process i in round r replaces MEB(T ) = B(CT , RT ) by B(CT , λRT ) and T (r) computes the inflated MEB-safe area SafeMEBi,λ = T ⊆P (r) B(CT , λRT ). In the following, we i

|T |≥n−t

establish two things: first, the candidate MEBs inflated by factor λ have a non-empty intersection, (r) so that the MEB-safe area SafeMEBi,λ is non-empty as well. This follows from Theorem 5.3, since n > 3t implies that p every three candidate MEBs intersect, so β = 3 and inflation factor λ is then at most λ ≤ 3/2. Second, we need to ensure that the contraction analysis of the Adaptive MEB Contraction Algorithm proved in Lemma 4.1 still holds for inflated balls. In fact, this holds, however increasing the balls weakens one inequality in Lemma 4.1, where the MEB-safe area is now contained in the smallest enclosing ball around correct processes inflated by factor λ. In this section, we also show that Adaptive MEB Contraction Algorithm on inflated candidate balls satisfies q 1+α2 λ 1+α2 −λ2 α2 -MEB-validity. Adaptive MEB Contraction Modification We use the same Adaptive MEB Contraction as shown in Algorithm 1, except that we replace Line 2 by the inflated MEB-safe area: (r)

SafeMEBi,λ =

B(CT , λRT )

(r) T ⊆Pi

|T |≥n−t

where B(CT , λRT ) denotes the smallest enclosing ball around subset T , with its radius increased by factor λ. Two changes are made at once. First the candidate MEBs are inflated, which provides a common intersection point if n > 3t. Second, the candidate subsets are of size at least n − t, instead of exactly n − t. This allows us to relate to the correct MEB inflated by λ, otherwise the containment (r) of MEB-safe area SafeMEBi,λ in the correct MEB inflated by λ is not guaranteed. Since every correct process receives all correct values and |H (r) | ≥ n − t, then the set H (r) is also a candidate

subset for every correct process, so its inflated ball B(Cr , λRr ) appears in the intersection. Hence, (r) locally computed MEB-safe areas are inside the correct MEB, i.e. SafeMEBi,λ ⊆ B(Cr , λRr ). (r)

All subsequent steps remain the same: each process initializes the diameter pair of SafeMEBi,λ (r)

and computes ci and ri . Then, it finds the farthest point of SafeMEBi,λ from ci and if necessary, adds it to the selected set and repeats the process. The Adaptive MEB Contraction Algorithm outputs ci and terminates, once the stopping criterion is satisfied. Note that, the inflation also restricts the √ admissible range of parameter α. Namely, as we show √ in Lemma 5.5, the contraction requires α < β − 1, which is α < 2 for n > 3t. We now apply Theorem 5.3 to the candidate MEBs to ensure the local MEB-safe areas have a non-empty intersection. Lemma 5.4. Assume the synchronous setting with t ≥ 1 and n > 3t, and let β =

n−1 t

and

β λ = β−1 . For every subset T ⊆ [n] of size at least n − t denote the smallest enclosing ball by MEB(T ) = B(CT , RT ), and let each correct process i compute the inflated local safe area T (r) SafeMEBi,λ = T ⊆P (r) B(CT , λRT ). Then in every round r there exists a common point pr i

|T |≥n−t (r) with pr ∈ SafeMEBi,λ for every correct process i. √ p

λ≤

3/2 <

Moreover, n > 3t implies β ≥ 3, and hence

(r)

Proof. Fix a round r and let Br = i∈H MEB(T ) : T ⊆ Pi , |T | ≥ n − t denote the family of all candidate MEBs computed by any correct process in round r. We first show that every subfamily of at most β balls from Br has a non-empty intersection. Let MEB(T1 ), . . . , MEB(Tℓ ) ∈ Br with ℓ ≤ β. Each Tj has size at least n − t and therefore excludes at most t processes, so the ℓ sets together exclude at most ℓt processes. Since ℓ ≤ β = ⌊ n−1 t ⌋, we have ℓt ≤ n − 1 and hence S

ℓ \ j=1

Tj = n −

ℓ [

[n] \ Tj

≥ n − ℓt ≥ 1.

j=1

Thus, the sets T1 , . . . , Tℓ have a common process. By consistent broadcast, this process contributes the same value to every set Tj , and hence this value lies in MEB(Tj ) for every j. This implies that every ℓ balls have a common intersection point. q β By Theorem 5.3, inflating the balls by factor λ = β−1 gives a common point pr contained in (r)

B(CT , λRT ), for every MEB(T ) ∈ Br . Since each SafeMEBi,λ is an intersection of a subfamily of (r)

these inflated balls, we obtain pr ∈ SafeMEBi,λ for every correct process i. √ p Finally, n > 3t gives β ≥ 3, so the factor λ is bounded by λ ≤ 3/2 < 2. q

β We proved that MEBs inflated by λ ≤ β−1 have a common intersection point. Next, we show that Adaptive MEB Contraction Algorithm modified for inflated candidate balls has a contraction λα rate √1+α and solves multidimensional approximate agreement. 2

Lemma 5.5. In the synchronous setting with n > 3t, the contraction rate of the Inflated Adaptive √ √ λα MEB Contraction Algorithm is Rr+1 ≤ √1+α R for 1 ≤ α < β − 1. In particular, α < 2 for r 2 n > 3t. Proof. Consider round r and let MEB(H (r) ) = B(Cr , Rr ). By Lemma 5.4, there exists a point pr , (r) such that pr ∈ SafeMEBi,λ for every correct process i. 20

(r)

We first show SafeMEBi,λ ⊆ B(Cr , λRr ). Due to consistent broadcast, every correct process (r)

receives all correct values, hence H (r) ⊆ Pi and |H (r) | ≥ n − t. The Inflated Adaptive MEB Contraction considers all subsets of size at least n − t, then the set of correct values H (r) is a candidate of every correct process. Its inflated ball B(Cr , λRr ) appears in the intersection defining (r) SafeMEBi,λ , hence the MEB-safe area is contained in B(Cr , λRr ). Now, fix a correct process i, and let Si be the selected set, ci the center of Si and ri the (r) radius computed by the Inflated Adaptive MEB Contraction Algorithm. Since Si ⊆ SafeMEBi,λ ⊆ B(Cr , λRr ) and B(ci , ri ) is the minimum enclosing ball around Si , we get: ∥ci − Cr ∥2 + ri2 ≤ λ2 Rr2 . (r)

When the Adaptive MEB Contraction Algorithm terminates, every point of SafeMEBi,λ lies within distance αri from ci . This also holds for the common point pr and we get ∥pr − ci ∥ ≤ αri , hence ri2 ≥ α12 ∥ci − pr ∥2 . These are Inequalities (1) and (2) from Lemma 4.1, where Rr is replaced by λRr . We apply the remaining steps of Lemma 4.1 verbatim with λRr instead of Rr and obtain ∥ci − ar ∥ ≤ √

λα Rr . 1 + α2

λα Rr ), As the point ar only depends on Cr and pr , every correct output lies in the ball B(ar , √1+α 2 λα centered in point ar with radius √1+α Rr . Therefore, the minimum enclosing ball of the new correct 2

λα values cannot have a larger radius than this ball, i.e. Rr+1 ≤ √1+α Rr . 2 √ √ √ λα 2 The factor √1+α2 < 1, when α < 1/ λ − 1 = β − 1. For n > 3t, this means that 1 ≤ α < 2.

At α = 1 the contraction rate is √λ2 ≤

√

3 2 ≈ 0.866.

β Theorem 5.6. Assume a synchronous setting with n > 3t and let β = ⌊ n−1 t ⌋, λ = β−1 and √ 1 ≤ α < β − 1, then the Inflated Adaptive MEB Contraction Algorithm solves multidimensional

approximate agreement after O

log(R √ max /ε) log( 1+α2 /(λα))

rounds and satisfies λ

1+α2 -MEB validity. 1+α2 −λ2 α2

Proof. We begin by showing the convergence, similarly to the proof of Theorem 5.1. In Lemma 5.5, r r λα λα λα √ √ we showed Rr+1 ≤ √1+α R . Over r rounds, R ≤ R ≤ R r r 0 max , where Rmax 2 1+α2 1+α2 is the known upper bound on the initial correct MEB radius. Since every correct value lies in MEB(H (r) ) = B(Cr , Rr ), any two correct values are at distance at most 2Rr ≤ ε. Hence, r λα √max /ε) rounds. 2 √1+α Rmax ≤ ε and ε-agreement is reached after log(2R 2 1+α2 log(

λα

)

Next, we show that the Inflated Adaptive MEB Contraction Algorithm satisfies λ 1+α1+α 2 −λ2 α2 MEB validity. As in Theorem 5.1, we bound the drift of the center and the contraction of the radius simultaneously, in the style of Inequality (6) for a suitable γ: ∥Cr+1 − Cr ∥ + γRr+1 ≤ γRr . In comparison to the Theorem 5.1, only the value of γ changes. From the proof of Lemma 5.5, for every correct output value ci we have ∥ci − Cr ∥2 + α12 ∥ci − 2 pr ∥ ≤ λ2 Rr2 , which is the corresponding inequality from Theorem 5.1 with λRr instead of Rr . Consequently, we define the point ar as in Theorem 5.1 and every correct output lies in B(ar , σr ), where σr2 =

λ2 Rr2 −

1 ∥Cr −pr ∥2 α2 +1 1 1+ 2 α

2 . The MEB containment inequality gives ∥Cr+1 − ar ∥2 + Rr+1 ≤ σr2 .

Using the consecutive steps and computations in the proof of Theorem 5.1 with λRr instead of Rr , we obtain v ∥Cr+1 − Cr ∥ + γRr+1

u u 1 + γ 2 + 12 α . ≤ λR t r

1 + α12

(1+α ) Solving this inequality, the smallest possible choice of γ is λ 1+α 2 −λ2 α2 . Note that γ ≥ 1. With this choice of γ, we obtain ∥Cr+1 − Cr ∥ + γRr+1 ≤ γRr for every two consecutive rounds r and r + 1. Further, we can use the proof of Theorem 5.1 verbatim the drift of the q and bound (1+α2 ) center of the MEB from C0 by induction to obtain ∥x − C0 ∥ ≤ λ 1+α2 −λ2 α2 , for every correct

value x ∈ H (r) . Hence, H (r) ⊆ B(C0 , λ q

Algorithm satisfies λ

(1+α2 ) R ), so the Inflated Adaptive MEB Contraction 1+α2 −λ2 α2 0

(1+α2 ) -MEB validity. 1+α2 −λ2 α2

√ Unlike in Theorem 5.1, the admissible range of α is now bounded by 2 and both the contraction rate and validity improve as α decreases. The following corollary highlights the resulting validity guarantees for particular choices of α. Corollary √5.7. For α = 1 the Inflated q Adaptive MEB Contraction Algorithm has contraction 2β 3 λ √ rate 2 ≤ 2 ≈ 0.866 and satisfies β−2 -MEB validity. In particular, for n > 3t it satisfies √ 6 ≈ 2.45-MEB validity. λα Remark 5.8. Substituting λ = 1 into the contraction factor √1+α of Lemma 5.5 and into the 2 q √ 1+α2 α validity constant λ 1+α2 −λ2 α2 of Theorem 5.6 recovers √1+α2 and 1 + α2 , and the admissible √ range α < β − 1 becomes unbounded, as in Theorem 5.1 (see Remark 4.3).

Asynchronous Approximate Agreement

We now turn to the asynchronous setting, where messages can be arbitrarily delayed and processes cannot wait for all correct values before proceeding with the computations. A process cannot distinguish a faulty process that never sends its value from a correct process whose message is delayed, so waiting for more than n − t values risks waiting forever. Consequently, a correct process may proceed without the values of some correct processes. Hence, each process invokes the Gather protocol [2, 16], which returns a local view containing a common-core GTHR of at least n − t values among all correct processes. However, a process does not know which of its values belong to the common-core. This is a weakness, compared to the synchronous setting, where every correct process received all correct values, so the set H (r) appeared in the candidate subsets and the MEB-safe area was compared to the correct minimum enclosing ball MEB(H (r) ). Under the Gather protocol, we only have a guarantee that there exists a common-core of size n − t. However, this common-core might be missing correct values, so it is not possible to compare the candidate subsets to the MEB(H (r) ). Instead, we compare the MEB-safe area to the minimum enclosing ball of the correct values a process received, and then relate that ball to MEB(H (r) ). First, we adapt the Adaptive MEB Contraction Algorithm to the asynchronous setting in Section 6.1 and analyze its contraction rate. Then, in Section 6.2 we show that this algorithm can be used to solve multidimensional approximate agreement in the asynchronous setting with resilience n > (d + 2)t, and in Section 6.3 with dimension-free resilience in the asynchronous setting, namely n > 4t.

6.1

Asynchronous Algorithm

In this section, we adapt the Adaptive MEB Contraction to the asynchronous setting. The algorithm is presented in Algorithm 2 and differs from Adaptive MEB Contraction Algorithm only in its first two lines. First, a process cannot wait for all correct values to arrive, since messages can be arbitrarily (r) delayed. Hence, each process invokes the Gather protocol, which returns a local view Pi for process i in round r. The Gather protocol guarantees that all correct processes receive a set GTHR(r) , named common-core, consisting of at least n − t values. However, different correct processes may therefore hold different local views, so no process knows which of its values belong to the common-core. Second, since the local views can differ in size, the candidate subsets are taken relative to the size (r) of the local view. Each process i intersects the minimum enclosing balls of all subsets T ⊆ Pi with (r) (r) |T | = |Pi | − t. Note that Pi contains at most t faulty values, so there exists at least one subset T consisting only of correct values. A natural alternative would be to fix the subset size to |T | = n − 2t, which is the smallest size any local view admits and would make all correct processes use subsets of same size. However, the disadvantage is that a process which received more values would then discard more of them than the t it must and its candidate subsets would omit correspondingly more of the common-core. Since it is the common-core that connects the local views of different processes together, this weakens the guarantee that their MEB-safe areas intersect and requires a stronger resilience assumption than n > (d + 2)t. We therefore only remove the t values a process cannot trust. All remaining steps are unchanged: each process initializes the selected set with the diameter of (r) SafeMEBi , then computes the center ci and radius ri , and repeatedly adds the farthest point of (r) SafeMEBi until the stopping criterion is satisfied. Algorithm 2 Asynchronous Adaptive MEB Contraction (for process i) √ (r) Require: Input value mi , threshold 1 ≤ α < 2 (r+1) Ensure: New input value mi (r) 1: Invoke Gather and obtain the local view Pi T (r) MEB(T ) 2: Compute the MEB-safe area SafeMEBi = (r) T ⊆P i (r)

3: Choose two diameter points: ai , bi ∈ arg max 4: Initialize the selected set Si ← ai , bi

|T |=|Pi

|−t (r)

x,y∈SafeMEBi

∥x − y∥

5: repeat 6: 7: 8:

if ∥qi − ci ∥ ≤ αri then (r+1) 10: return mi ← ci 11: else 12: Add this point: Si ← Si ∪ {qi } 13: end if (r) 14: until all points of SafeMEBi are within radius αri 9:

6.2

Resilience n > (d + 2)t

In the following, q we show that the contraction factor of Asynchronous Adaptive MEB Contraction 2 Algorithm is α 2+α 2 . Note that the contraction factor does not depend on dimension d, only on √ the parameter α, which takes values from 1 to 2. √ Lemma 6.1. In the asynchronous setting with n > (d + 2)t and 1 ≤ α < q 2, the contraction rate 2 of the Asynchronous Adaptive MEB Contraction Algorithm is Rr+1 ≤ α 2+α 2 Rr . Proof. Let H (r) denote the values of correct processes in round r, and let MEB(H (r) ) = B(Cr , Rr ) be the minimum enclosing ball around the correct values. Moreover, let Rr+1 denote the radius of the minimum enclosing ball around the new correct values after all correct processes output their ci . We first show that all locally computed MEB-safe areas have a common point. Consider the family of all candidate balls computed by correct processes in round r: Br =

[ n

(r)

MEB(T ) : T ⊆ Pi , |T | = |Pi | − t .

i∈H

We show that every d + 1 balls in Br have a nonempty intersection. Take any d + 1 sets T1 , . . . , Td+1 (r) (r) defining such balls. For every j there is a correct process πj with Tj ⊆ Pπj and |Tj | = |Pπj | − t. By the Gather protocol, there exists a common-core GTHR(r) of values from at least n − t senders, (r) (r) with GTHR(r) ⊆ Pπj for every j. Since Tj is obtained by removing exactly t values from Pπj , it can omit at most t values from GTHR(r) , i.e. |GTHR(r) \ Tj | ≤ t. From the union we obtain: GTHR(r) ∩

d+1 \ j=1

Tj ≥ |GTHR(r) | −

d+1 X

|GTHR(r) \ Tj | ≥ (n − t) − (d + 1)t = n − (d + 2)t > 0.

j=1

Hence, there is a sender, whose value is contained in all T1 , . . . , Td+1 and this value lies in all minimum enclosing balls defined on these sets. Every d + 1 balls therefore intersect and by Helly’s theorem [18] the whole family of candidate balls has a nonempty intersection. Consequently, all (r) locally computed MEB-safe areas intersect, so there exists a point pr such that pr ∈ SafeMEBi for every correct process i. (r) Unlike in the synchronous case, we cannot directly compare the MEB-safe area SafeMEBi to the correct minimum enclosing ball MEB(H (r) ) because process i may not receive all correct (r) values. Instead, we compare SafeMEBi to the MEB of the correct values received by process (r) (r) (r) b i,r ) i. Let Hi be the set of correct values contained in Pi and write MEB(Hi ) = B(Cbi,r , R (r) (r) b i,r . We now show that SafeMEB ⊆ MEB(H ). At most t values centered in Cbi,r with radius R i i (r) (r) (r) in Pi are Byzantine, so |Hi | ≥ |Pi | − t. Next, let Di be the set of points which defines the (r) (r) MEB(Hi ). Since at most d + 1 points can define a ball, then |Di | ≤ d + 1. From |Pi | ≥ n − t, (r) (r) we have |Pi | − t ≥ n − 2t and together with n > (d + 2)t, this gives |Pi | − t ≥ d + 1. Hence, (r) (r) (r) we can extend Di to a subset consisting only of correct values Ui ⊆ Hi of size |Pi | − t. From (r) (r) (r) (r) (r) Di ⊆ Ui ⊆ Hi , we get MEB(Ui ) = MEB(Hi ) and since Ui is one of the candidate subsets (r) computed by process i, its minimum enclosing ball appears in the intersection defining SafeMEBi , (r) (r) so SafeMEBi ⊆ MEB(Hi ). In Asynchronous Adaptive MEB Contraction Algorithm, each process i maintains a selected set (r) Si in SafeMEBi and computes the point that minimizes the largest distance to the selected points denoted by ci . Since all selected points are within distance ri from ci , we have Si ⊆ B(ci , ri ), and 24

(r)

b i,r ). because Si ⊆ SafeMEBi ⊆ MEB(Hi ), the set Si is also contained in MEB(Hi ) = B(Cbi,r , R Since B(ci , ri ) is the smallest ball which contains Si : b2 . ∥ci − Cbi,r ∥2 + ri2 ≤ R i,r

(18)

(r)

Applying the same argument Hi ⊆ H (r) ⊆ MEB(H (r) ) relates the locally computed correct ball (r) MEB(Hi ) to the correct MEB(H (r) ) = B(Cr , Rr ): b 2 ≤ R2 . ∥Cbi,r − Cr ∥2 + R i,r r

(19) (r)

Next, Asynchronous Adaptive MEB Contraction Algorithm stops only when every point of SafeMEBi is within distance αri from ci . This also holds for the common point pr , so ∥pr − ci ∥ ≤ αri and ri2 ≥

1 ∥ci − pr ∥2 . α2

(20)

Similarly to the proof of Lemma 4.1, plugging in Inequality 20 into Inequality 18 and eliminating b 2 with Inequality 19, we obtain R i,r ∥ci − Cbi,r ∥2 + ∥Cbi,r − Cr ∥2 +

1 ∥ci − pr ∥2 ≤ Rr2 . α2

(21)

Using the parallelogram law on the first two terms of Inequality 21, we get 1 1 ∥ci − Cr ∥2 + 2 ∥ci − pr ∥2 ≤ Rr2 2 α

(22)

which is analogous to the Inequality 3 in Lemma 4.1. Note that the coefficient of ∥ci − Cr ∥2 dropped (r) from 1 to 1/2 which is the result of comparing the SafeMEBi to the local ball instead of directly to MEB(H (r) ). Along the lines of Lemma 4.1, we define ar as the weighted midpoint between Cr and pr , i.e. ar = ( 21 Cr + α12 pr )/( 12 + α12 ). Thus, 1 1 ∥ci − Cr ∥2 + 2 ∥ci − pr ∥2 = 2 α Hence, ∥ci − ar ∥ ≤ α

2 R . 2+α2 r

centered in ar with radius α

1 1 1 + 2 ∥ci − ar ∥2 + 2 ∥Cr − pr ∥2 ≤ Rr2 . 2 α α +2

So every correct output ci lies inside the ball B(ar , α

(23) 2 R ), 2+α2 r

2 R . Therefore, the minimum enclosing ball of the new correct 2+α2 r q 2 values cannot have a larger radius than this ball, i.e. Rr+1 ≤ α 2+α 2 Rr . This factor is smaller

than one exactly when α <

√

We contraction rate of Asynchronous Adaptive MEB Contraction Algorithm q showed that the √ 2 is α 2+α for 1 ≤ α < 2. Note that the contraction is dimension-independent. Next, we show 2 that Asynchronous Adaptive MEB Contraction Algorithm solves multidimensional approximate agreement under MEB-validity. √ Theorem 6.2. Assume n > (d + 2)t and 1 ≤ α < 2. Then Asynchronous Adaptive   MEB √max /ε)  rounds Contraction Algorithm solves multidimensional approximate agreement after O  log(R 2+α2 log

and satisfies

2(α2 +2) -MEB validity. 2−α2

√ α 2

Proof. We first show the convergence. In Lemma 6.1, we showed that the radius of the minimum q √ 2 enclosing ball shrinks Rr+1 ≤ α 2+α2 Rr , with 1 ≤ α < 2. The argument of Theorem 5.1 applies 



verbatim with contraction factor α

log(2R 2 √max /ε)  rounds. This and gives convergence after   2  2+α2 √   log 2+α α 2

proves convergence and termination. q 2 +2) Next, we show that Asynchronous Adaptive MEB Contraction Algorithm satisfies 2(α 2−α2 MEB validity. As in Theorem 5.1, we bound the drift of the center and the contraction of the radius simultaneously and establish ∥Cr+1 − Cr ∥ + γRr+1 ≤ γRr (24) for a suitable γ ≥ 1. Once this holds, the induction of Theorem 5.1 gives H (r) ⊆ B(C0 , γR0 ) for every round r. From Lemma 6.1 we have 12 ∥ci −Cr ∥2 + α12 ∥ci −pr ∥2 ≤ Rr2 for every output ci and with the point ar 2

∥Cr −pr ∥ 2 as defined there, every correct output lies inside the ball B(ar , σr ), where σr2 = α2α 2 +2 Rr − α2 +2 2

Hence, all new correct inputs lie inside the ball H (r+1) ⊆ B(ar , σr ) and the MEB containment 2 inequality gives ∥Cr+1 − ar ∥2 + Rr+1 ≤ σr2 . We now bound the validity factor γ. By the triangle inequality, ∥Cr+1 − Cr ∥ + γRr+1 ≤ ∥ar − Cr ∥ + ∥Cr+1 − ar ∥ + γRr+1 . Using the definition of ar for the first term on the right side, using Cauchy-Schwarz and definition of σr for the second and third term gives: 2∥pr − Cr ∥ q ∥Cr+1 − Cr ∥ + γRr+1 ≤ + 1 + γ2 α2 + 2

2α2 2α2 2− R ∥pr − Cr ∥2 . r α2 + 2 (α2 + 2)2

(25)

2 2 + 1 + γ 2 α2α 2 +2 ≤ γ. Solving this inequality α2 q 2 +2) gives the smallest possible choice of γ, that is γ = 2(α . Plugging γ into Inequality (24) and 2−α2 performing the same analysis as in the proof of Theorem 5.1qwe get H (r) ⊆ B(C0 , γR0 ). Thus, 2 +2) -MEB validity. Asynchronous Adaptive MEB Contraction Algorithm satisfies 2(α 2−α2

Hence, it is enough to choose a γ such that

Corollary 6.3. For α = 1, the contraction factor is validity.

2 3

and the algorithm satisfies

√

6-MEB

We next consider the resilience case n > 4t, which removes the dependence on the dimension d. As in the synchronous setting, we inflate the candidate balls by a factor λ > 1 to obtain a common intersection point. The counting argument above shows that under Gather protocol every l candidate balls intersect when n > (l + 1)t, so for n > 4t every three balls intersect. Therefore, we apply Theorem 5.3 with β = 3. We also enlarge the family of candidate subsets, as in Section 5.3, since the containment of the locally computed safe area SafeMEB in the correct MEB cannot be obtained by extending a defining set.

6.3

Multidimensional Approximate Agreement with Resilience n > 4t

In order to get the intersection of the candidate balls, we must first modify Asynchronous Adaptive MEB Contraction Algorithm and inflate the candidate balls’ radius by a factor λ > 1. The modification is similar to the modification done for Adaptive MEB Contraction Algorithm in the synchronous setting. 26

Inflated Adaptive MEB Contraction We use the same Asynchronous Adaptive MEB Contraction as shown in Algorithm 2, except that we replace Line 2 by the inflated MEB-safe area (r)

SafeMEBi,λ =

B(CT , λRT )

(r) T ⊆Pi (r) |T |≥|Pi |−t

where B(CT , λRT ) denotes the smallest enclosing ball around subset T with its radius increased by factor λ. Two changes are made at once. First, the candidate MEB balls are inflated, which provides a common intersection point when n > 4t. Second, the candidate subsets are of size at (r) (r) least |Pi | − t, instead of exactly |Pi | − t. This allows us to relate the inflated MEB-safe area (r) to the MEB of the correct values received by process i. Indeed, if Hi denotes the set of correct (r) (r) (r) (r) values contained in Pi , then |Hi | ≥ |Pi | − t. Hence, Hi is itself a candidate subset and its (r) inflated ball appears in the intersection defining the safe area SafeMEBi,λ . All subsequent steps remain the same: each process initializes the selected set with the diameter (r) (r) pair of SafeMEBi,λ and computes ci and ri . Then it repeatedly adds the farthest point of SafeMEBi,λ until the stopping criterion is satisfied. Note that range of α. As we show below, the contraction q the inflation restricts the admissible √ p 1+λ2 1+λ2 requires λα 1+λ2 +α2 λ2 < 1, which is α < λ2 . For the guaranteed inflation factor λ = 3/2, √

the bound on α becomes 1 ≤ α < 310 . Next, we show that increasing the radius of candidate balls provides a common intersection point. Lemma q the asynchronous setting using the Gather protocol and n > 4t. Let β = k 6.4. Assume j β n−t−1 and λ = t β−1 . Then, in every round r, there exists a common point pr such that (r)

pr ∈ SafeMEBi,λ for every correct process i. In particular, n > 4t implies β ≥ 3, and hence p λ ≤ 3/2. (r)

(r)

Proof. Fix a round r and let Br = i∈H MEB(T ) : T ⊆ Pi , |T | ≥ |Pi | − t denote the family of all candidate MEBs computed by any correct process in round r. We first show that every subfamily of at most β balls from Br has a non-empty intersection. Take any ℓ ≤ β candidate sets T1 , . . . , Tℓ , (r) (r) where for each j ∈ {1, . . . , ℓ} there is a correct process πj such that Tj ⊆ Pπj and |Tj | ≥ |Pπj | − t. By the Gather protocol, there exists a common-core GTHR(r) of values from at least n − t senders, (r) (r) with GTHR(r) ⊆ Pπj for every j. Since Tj excludes at most t values from Pπj , it also omits at most t values from GTHR(r) , that is |GTHR(r) \ Tj | ≤ t. Therefore, S

GTHR(r) ∩

ℓ \ j=1

Tj ≥ |GTHR(r) | −

ℓ X

|GTHR(r) \ Tj | ≥ (n − t) − ℓt ≥ 1.

j=1

Thus, there is a process whose value is contained in all sets T1 , . . . , Tℓ and this value lies in each of the balls MEB(T1 ), . . . , MEB(Tℓ ). Therefore, every β balls from Br intersect p and for n > 4t we can apply Theorem 5.3 with β = 3. Inflating every ball by a factor λ = 3/2 gives a common (r) intersection point pr with pr ∈ B(CT , λRT ) for every MEB(T ) ∈ Br . Since each SafeMEBi,λ is an (r)

intersection of a subfamily of these inflated balls, we get pr ∈ SafeMEBi,λ for every correct process i.

β We proved that the MEBs inflated by λ ≤ β−1 have a common intersection point. Next, we show that the Inflated Asynchronous Adaptive MEB Contraction Algorithm for inflated candidate q 1+λ2 balls provides a contraction rate λα 1+λ2 +α2 λ2 and solves multidimensional approximate agreement.

Lemma 6.5. In the asynchronous setting with n > 4t, the contraction rate of the Inflated √Asynq 2 1+λ2 chronous Adaptive MEB Contraction Algorithm is Rr+1 ≤ λα 1+λ2 +α2 λ2 Rr for 1 ≤ α < 1+λ . λ2 In particular, 1 ≤ α <

√

10 3 for n > 4t.

Proof. Let MEB(H (r) ) = B(Cr , Rr ) be the minimum enclosing ball around correct values in round (r) r. By Lemma 6.4 there exists a point pr with pr ∈ SafeMEBi,λ for every correct process i. We first relate the inflated safe area to the MEB of the correct values received by process i. Fix a (r) (r) correct process i and let Hi be the set of correct values contained in the local view Pi and write (r) b i,r ). At most t values in the local view are Byzantine, so |H (r) | ≥ |P (r) | − t. MEB(Hi ) = B(Cbi,r , R i i Next, the Inflated Asynchronous Adaptive MEB Contraction Algorithm considers all subsets of (r) (r) size at least |Pi | − t, and therefore Hi is one of the candidate subsets. Hence, its inflated ball (r) (r) b i,r ). Using appears in the intersection defining SafeMEBi,λ and we get SafeMEBi,λ ⊆ B(Cbi,r , λR (r)

the Inequality (19) from Lemma 6.1, the local correct MEB(Hi ) relates to the correct MEB(H (r) ) with b 2 ≤ R2 . ∥Cbi,r − Cr ∥2 + R i,r r The remaining steps follow from Lemma 6.1. The selected set from the Inflated Asynchronous (r) b i,r ) and since B(ci , ri ) Adaptive MEB Contraction Algorithm satisfies Si ⊆ SafeMEBi,λ ⊆ B(Cbi,r , λR is its minimum enclosing ball, gives b2 . ∥ci − Cbi,r ∥2 + ri2 ≤ λ2 R i,r

The stopping criterion also holds for the common point pr , hence ri2 ≥ α12 ∥ci − pr ∥2 . Combining these inequalities, we get ∥ci − Cbi,r ∥2 + λ2 ∥Cbi,r − Cr ∥2 +

1 ∥ci − pr ∥2 ≤ λ2 Rr2 . α2

(26)

In contrast to Inequality (21), the middle term is multiplied by the inflation factor. Thus, we 1 λ2 λ2 1 perform the same step and define ar = ( 1+λ 2 Cr + α2 pr )/( 1+λ2 + α2 ). Completing the square in Inequality (23) and dropping the non-negative term containing ∥Cr − pr ∥2 gives: s

∥ci − ar ∥ ≤ λα

1 + λ2 Rr . 1 + λ 2 + α 2 λ2

So, every correct output ci lies inside the ball B(ar , λα

1+λ2 R ), centered in ar with radius 1+λ2 +α2 λ2 r

1+λ2 R . Therefore, the minimum enclosing ball of the new correct values cannot have 1+λ2 +α2 λ2 r q 2 a larger radius, i.e. Rr+1 ≤ λα 1+λ1+λ 2 +α2 λ2 Rr . This factor is smaller than one exactly when √ 2 . α < 1+λ λ2

λα

We showed that q the contraction rate of√the Inflated Asynchronous Adaptive MEB Contraction 2 1+λ2 Algorithm is λα 1+λ1+λ . Next, we show that the Inflated Asynchronous 2 +α2 λ2 for 1 ≤ α < λ2 Adaptive MEB Contraction Algorithm solves multidimensional approximate agreement under MEBvalidity. 28

Theorem 6.6. Assume asynchronous setting with n > 4t, and let β = and 1 ≤ α <

√

1+λ2 . λ2

n−t−1 t

, λ =

β β−1

Then, the Inflated AsynchronousAdaptive MEB Contraction Algorithm 

solves multidimensional approximate agreement after O 

log

log(R √ max /ε)  rounds and satisfies 1+λ2 +α2 λ2 √ 1+λ2

λα

(1+λ2 )(1+λ2 +α2 λ2 ) -MEB validity. 1+λ2 −α2 λ4

In Lemma 6.5, we showed that the radius of the miniProof. We first show the convergence. q √ 1+λ2 1+λ2 mum enclosing ball shrinks Rr+1 ≤ λα 1+λ2 +α2 λ2 Rr with 1 ≤ α < λ2 . The argument of Theorem 5.1 applies verbatim with contraction factor λα

1+λ2 and gives convergence after 1+λ2 +α2 λ2





log(2R  √ max /ε)  rounds. This proves convergence and termination.  2 2 2   log 1+λ√ +α 2λ  λα

1+λ

we show that the Inflated Asynchronous Adaptive MEB Contraction Algorithm satisfies q Next, (1+λ2 )(1+λ2 +α2 λ2 ) -MEB validity. As in Theorem 5.1, we bound the drift of the center and the 1+λ2 −α2 λ4 contraction of the radius simultaneously and establish ∥Cr+1 − Cr ∥ + γRr+1 ≤ γRr

(27)

for a suitable γ ≥ 1. Once this holds, the induction of Theorem 5.1 gives H (r) ⊆ B(C0 , γR0 ) for every round r. From the proof of Lemma 6.5, every correct output lies in B(ar , σr ), with 2 α2 λ2 (1+λ2 ) 2 2 σr2 = λ2 α2 1+λ1+λ 2 +α2 λ2 Rr − (1+λ2 +α2 λ2 )2 ∥Cr − pr ∥ . Hence, all new correct values lie inside the 2 ball H (r+1) ⊆ B(ar , σr ), and the MEB containment inequality gives ∥Cr+1 − ar ∥2 + Rr+1 ≤ σr2 . We now bound the validity factor γ. By the triangle inequality, we get ∥Cr+1 − Cr ∥ + γRr+1 ≤ ∥ar − Cr ∥ + ∥Cr+1 − ar ∥ + γRr+1 . Using the definition of ar for the first term on the right side, using Cauchy-Schwarz and definition of σr for the second and third term gives:

∥Cr+1 − Cr ∥ + γRr+1 ≤ +

(1 + λ2 )∥pr − Cr ∥ 1 + λ 2 + α 2 λ2 q

1 + γ 2 λ2 α2

(28)

1 + λ2 α2 λ2 (1 + λ2 ) 2− R ∥pr − Cr ∥2 . r 1 + λ2 + α2 λ2 (1 + λ2 + α2 λ2 )2 q

(29)

2 1+λ2 + 1 + γ 2 λ2 α2 1+λ1+λ 2 +α2 λ2 ≤ γ. After α 2 λ2 q 2 )(1+λ2 +α2 λ2 ) solving this inequality, the smallest possible choice of γ is γ = (1+λ1+λ . Note that the 2 −α2 λ4 √ 2 denominator is positive because α < 1+λ . Next we plug in γ into Inequality 27 and perform λ2 the same analysis as in the proof of Theorem 5.1. We get H (r)q⊆ B(C0 , γR0 ). Thus, the Inflated 2 )(1+λ2 +α2 λ2 ) Asynchronous Adaptive MEB Contraction Algorithm satisfies (1+λ1+λ -MEB validity. 2 −α2 λ4

Hence, it is enough to choose a value of γ such that

Corollary 6.7. For n > 4t, we have β ≥ 3 hence λ ≤ 3/2, so the admissible range for α is √ 10 1 ≤ α < 3 ≈ 1.054. For α = 1, the Inflated Asynchronous Adaptive MEB Contraction Algorithm √ √ has contraction factor 415 ≈ 0.968 and satisfies 2 10 ≈ 6.32-MEB validity. p

The range of admissible range for α is for n > 4t narrow, so α can be chosen only slightly above one. As fraction nt grows, β increases and λ approaches one, so the admissible range broadens to √ 1 ≤ α < 2. 29

Remark 6.8. Substituting λ = 1 into and into the validity q 2 factor of Lemma 6.5 q the contraction √ √ 2(α +2) 2 1+λ2 constant of Theorem 6.6 recovers α 2+α2 and . The bound α < λ2 becomes α < 2, 2−α2 as in Lemma 6.1 and Theorem 6.2. In contrast to the √ synchronous case, the admissible range for α remains bounded even at λ = 1. This restriction α < 2 is imposed by the Gather protocol rather than by ball inflation.

Discussion and Future Work

In this section, we first show that the contraction analysis of the Adaptive MEB √ Contraction Algorithm is tight. For this, we give an example in which the contraction factor 1/ 2 for α = 1 is achieved exactly. We then turn to Minimum-Diameter Averaging (MDA), another multidimensional approximate agreement algorithm with dimension-free contraction and strong resilience guarantees. Since MDA is known not to satisfy convex nor box validity, we derive the MEB-validity guarantees implied by its known diameter contraction bounds. This allows us to compare MDA with our algorithms under a common validity notion. Finally, we discuss the computational aspects of our approach. Tightness of the contraction analysis. The factor √12 in Lemma 4.1 is tight for the geometric analysis of Adaptive MEB Contraction with α = 1. Consider one round with n = 7, t = 2, and d = 2. Let the five correct values be H (r) = {(−1, 0), (0, 0), (0, 0), (0, 0), (1, 0)}. Thus, MEB(H (r) ) = B((0, 0), 1), so Cr = (0, 0) and radius Rr = 1. Let the two Byzantine values be b+ = (1, 1) and b− = (−1, −1). Suppose that correct processes with values (0, 0), (1, 0) have local view P + = H (r) ∪ {b+ }, while correct process with value (−1, 0) has local view P − = H (r) ∪ {b− }. Since n − t = 5, the local MEB-safe area is the intersection of the MEBs of all subsets of size n − t = 5 of the corresponding local view. We first consider correct processes with local view P + . The distinct candidate are balls B0 = B((0, 0), 1) coming from the subset containing only correct values, then B1 = B 21 , 12 , √12 , coming from the subset {(0, 0), (1, 0), (1, 1)} and B2 = B

√

0, 12 , 25

coming from subsets that

contain {(−1, 0), (0, 0), (1, 1)}. Hence SafeMEB = B0 ∩ B1 ∩ B2 . The three points (0, 0), (1, 0), and (0, 1) all belong to SafeMEB+ . Moreover, SafeMEB+ ⊆ B1 , and these threepoints have + minimum enclosing ball exactly B1 . Therefore, MEB(SafeMEB ) = B 12 , 12 , √12 . Thus, for +

α = 1, Adaptive MEB Contraction Algorithm outputs c+ = 21 , 12 . − By symmetry, a process with local view P computes a safe area whose minimum enclosing 1 1 1 1 1 − ball is B − 2 , − 2 , √2 , and outputs c = − 2 , − 2 . Hence the new correct values contain √ c+ and c√− , whose distance is ∥c+ − c− ∥ = 2. Consequently, the new correct MEB has radius √ Rr+1 = 22 = √12 Rr . Thus, the contraction factor 1/ 2 is achieved. The example is illustrated in Figure 2. Comparison with Minimum-Diameter Averaging. Another well-known approximate agreement algorithm is Minimum-Diameter Averaging (MDA) [22]. MDA is particularly relevant in our setting because, like our algorithms, it provides a dimension-free contraction. However, MDA is analysed in terms of diameter rather than radius contraction and it is known to satisfy strong validity but neither box nor convex validity [12]. In this section, we therefore derive the MEB-validity guarantee that follows from MDA’s diameter contraction and compare it to our algorithm.

Right local view

Left local view

(1, 1)

(0, 1)

cR = ( 21 , 12 ) (−1, 0)

(0, 0)

(1, 0)

(−1, 0) cL = (− 12 , − 12 ) (−1, −1)

(1, 0)

(0, −1)

Figure 2: Tight example showing that the α = 1 contraction analysis achieves √12 contraction

factor. The right and left local MEB-safe areas are symmetric and produce outputs cR = ( 12 , 12 ) and √ √ √ cL = (− 21 , − 12 ). Hence ∥cR − cL ∥ = 2, so the new correct MEB has radius Rr+1 = 1/ 2 = Rr / 2. Correct values are shown as black points , while Byzantine values are shown as red squares . Candidate MEBs are shown with dashed lines and the MEB-safe area is highlighted in blue. The points (0, 1) and (0, −1) shown as are not input values; they are illustrated only to make the boundary of the MEB-safe areas visible. Definition 7.1 (MDA). Let P = {m1 , . . . , mn } ⊂ Rd and let t be the maximal number of Byzantine processes. Define the diameter of a set M ⊆ P as DM = maxmi ,mj ∈M ∥mi −mj ∥. An MDA output is 1 P obtained as follows: choose a subset M ∈ arg min M ⊆P DM , and output M DA = |M mi ∈M mi . | |M |=n−t

MDA selects a minimum-diameter subset of received values and outputs their average. Cambus and Melnyk [12] show that in the synchronous case, MDA tolerates up to n > 4t Byzantine processes and has contraction rate Dr+1 ≤ 23 Dr , where Dr denotes the diameter of correct processes in round r. In the asynchronous case, authors in [22], show that MDA has n > 7t resilience and contraction factor Dr+1 ≤ 45 Dr . There, a process does not apply MDA to all n values. Instead, it (r)

(r)

applies MDA to its local view Pi , where q = |Pi |, and selects a minimum-diameter subset of size (r) q − t = |Pi | − t. Lemma 7.2. In the synchronous setting with n > 4t, MDA satisfies 7-MEB validity. In the (r) asynchronous setting of El-Mhamdi et al. [22], where process i applies MDA to its local view Pi (r) and selects a subset of size |Pi | − t, MDA satisfies 11-MEB validity under the contraction bound Dr+1 ≤ 45 Dr . Proof. Let Dr denote the diameter of the correct values in round r, let MEB(H (0) ) = B(C0 , R0 ), and let Lr = maxx∈H (r) ∥x − C0 ∥ be the smallest radius with H (r) ⊆ B(C0 , Lr ), so that L0 ≤ R0 . In other words, Lr measures how far the current correct values in round r have drifted from the correct MEB’s center C0 . Let qMDA < 1 denote the contraction factor of MDA, i.e., Dr+1 ≤ qMDA Dr . In the synchronous setting, qMDA = 32 [12], whereas in the asynchronous setting [22], qMDA = 45 . (r)

Fix a round r and consider the output of a correct process i. Let Pi be the set of values used by process i in this round, and let M be the subset selected by MDA. In the synchronous setting, (r) Pi contains all n values and MDA selects a subset of size n − t. In the asynchronous setting of (r) El-Mhamdi et al. [22], process i applies MDA to its local view Pi and selects a subset of size (r) |Pi | − t. Let DM be the diameter of the subset M . 31

In both settings, obtaining a local subset containing only correct values is feasible. In the synchronous model, due to consistent broadcast, it is guaranteed that all correct processes receive all correct values. Hence, a correct process locally computes a subset of size n − t consisting of (r) (r) correct values only. In the asynchronous setting, at most t values in Pi are Byzantine, so Pi (r) (r) contains at least |Pi | − t correct values. So obtaining a subset of correct values of size |Pi | − t is feasible. Since every subset containing only correct values has diameter at most Dr and the set M has minimum diameter, we have DM ≤ Dr . Moreover, M contains at least one correct value, since the selected subset has size larger than t and at most t values are Byzantine. Consider one such correct value and name it h. Since DM is the diameter of M , every value in M lies within distance at most DM from h. So, the subset M lies inside the ball centered at h with radius DM , i.e. M ⊆ B(h, DM ). As B(h, DM ) is convex and the MDA output is the average of the values in M , the output lies in B(h, DM ) as well, hence at distance at most Dr from h. Since h ∈ H (r) ⊆ B(C0 , Lr ), the triangle inequality implies that every correct value in round r + 1 lies in B(C0 , Lr + Dr ). Hence, Lr+1 ≤ Lr + Dr . Iterating over rounds 0, . . . , r − 1 and using k the contraction Dk ≤ qMDA D0 we obtain: Lr ≤ L0 +

r−1 X

Dk ≤ R0 + D0

k=0

∞ X k=0

k qMDA = R0 +

D0 . 1 − qMDA

Since D0 ≤ 2R0 , we obtain Lr ≤ 1 + 1−q2MDA R0 . For synchronous MDA, qMDA = 23 , so MDA satisfies 7-MEB validity. For asynchronous MDA, qMDA = 45 , so MDA satisfies 11-MEB validity. The validity guarantee is obtained by summing over drift in each round via geometric series. Our bounds instead control the drift of the center and the contraction of the radius simultaneously, as discussed after Theorem 5.1, and are correspondingly√smaller. For the synchronous setting, the bound for Adaptive MEB Contraction Algorithm is 6-MEB validity with resilience n > 3t, whereas MDA has resilience n > 4t and satisfies 7-MEB validity. In the asynchronous setting, we √ achieve 2 10-MEB validity with resilience n > 4t. In contrast, MDA satisfies 11-MEB validity and has resilience n > 7t. Computational Aspects and Future Work. As is standard in distributed computing and agreement algorithms analysis, our results in Theorems 5.1, 5.6, 6.2 and 6.6 are focused on round complexity rather than on the local computation performed in each round. The number of communication rounds follows directly from the contraction factor and is logarithmic in the ratio between the initial radius and the target distance ε. The local computation in each round can, however, be expensive. Every algorithm of this type, such as Mendes–Herlihy and Vaidya–Garg [35], n pays for computing a safe area and the cost is dominated by the t candidate subsets. In our algorithms the safe area region is an intersection of minimum enclosing balls. Our Adaptive MEB Contraction algorithm is inspired by the core-set construction of Bădoiu and Clarkson [6, 7]. In each iteration, the algorithm computes the minimax center of the current selected set Si and then queries the MEB-safe area for a point farthest from this center. The difference from the standard core-set setting is that this farthest point is not chosen from a finite input set, but (r) from the continuous region SafeMEBi . Thus, an exact implementation requires optimization over √ the safe area. The parameter α controls how often this query is needed. By Lemma 4.4, for α = 3 the initial diameter pair already satisfies the stopping criterion, so no additional queries for the farthest point is required. Smaller values of α improve the contraction factor, however they may require more iterations. Thus, α gives a trade off between local computation and round complexity. 32

The inflated variants of the Adaptive MEB Contraction algorithm have an additional computational overhead. To obtain the containment of the MEBs needed for the analysis, we intersect over all (r) subsets of size at least n − t in the synchronous case, and at least |Pi | − t in the asynchronous case. This enlarges the family of candidate balls and can make a direct implementation substantially more expensive. The question whether the intersection of the minimum enclosing balls over all subsets of size exactly n − t consisting only of correct values is already contained in MEB(H (r) ) remains open. Our goal in this work was to achieve better resilience bounds and we have not optimized the resulting computation. Designing efficient implementations and approximation routines for the inflated MEB-safe areas remains an important direction for future work.

Acknowledgments Research supported by the German Research Foundation (DFG), Schwerpunktprogramm SPP 2378: Resilience in Connected Worlds: Mastering Failures, Overload, Attacks, and the Unexpected, ReNO-2 (511099228), 2025-2029.

AI Disclosure We used ChatGPT and Claude (Anthropic) to assist with the written presentation and clarity of the paper. All technical results, definitions, algorithms and proofs originate from the authors, who verified the correctness and originality of all content including references.

References [1] Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approximate agreement. In Proceedings of the 8th International Conference on Principles of Distributed Systems, OPODIS’04, page 229–239, Berlin, Heidelberg, 2004. Springer-Verlag. [2] Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. Reaching consensus for asynchronous distributed key generation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 363–373, 2021. [3] Karim Adiprasito, Imre Bárány, Nabil H Mustafa, and Tamás Terpai. Theorems of carathéodory, helly, and tverberg without dimension. Discrete & Computational Geometry, 64(2):233–258, 2020. [4] Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. Frugal byzantine computing. arXiv preprint arXiv:2108.01330, 2021. [5] Hagit Attiya, Itay Flam, and Jennifer L Welch. Brief announcement: communication patterns for optimal resilience. In 39th International Symposium on Distributed Computing (DISC 2025), pages 46–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025. [6] Mihai Badoiu and Kenneth L Clarkson. Smaller core-sets for balls. In SODA, volume 3, pages 801–802, 2003. [7] Mihai Bădoiu and Kenneth L Clarkson. Optimal core-sets for balls. Computational Geometry, 40(1):14–22, 2008.

[8] Akhil Bandarupalli, Adithya Bhat, Somali Chaterji, Michael K Reiter, Aniket Kate, and Saurabh Bagchi. Sensorbft: Fault-tolerant target localization using voronoi diagrams and approximate agreement. In 2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS), pages 186–197. IEEE, 2024. [9] Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC ’83, page 27–30, 1983. [10] Gabriel Bracha. Asynchronous byzantine agreement protocols. Inf. Comput., 75(2):130–143, November 1987. [11] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference, pages 524–541. Springer, 2001. [12] Mélanie Cambus and Darya Melnyk. Centroid approximation with multidimensional approximate agreement protocols. In Stabilization, Safety, and Security of Distributed Systems, pages 93–110, 2026. [13] Mélanie Cambus, Darya Melnyk, Tijana Milentijević, and Stefan 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. [14] Melanie Cambus, Darya Melnyk, Tijana Milentijevic, and Stefan Schmid. Coordinate-wise median in byzantine federated learning. In Proceedings of the International Workshop on Secure and Efficient Federated Learning, FL-AsiaCCS ’25, New York, NY, USA, 2025. Association for Computing Machinery. [15] Mélanie Cambus, Darya Melnyk, Tijana Milentijević, and Stefan Schmid. Practical validity conditions for byzantine-tolerant federated learning, 2026. [16] Ran Canetti and Tal Rabin. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 42–51, 1993. [17] Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. On the validity of consensus. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC ’23, page 332–343, 2023. [18] Ludwig Danzer, Branko Grünbaum, and Victor Klee. Helly’s theorem and its relatives1 . In Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, volume 7, page 101. American Mathematical Soc., 1963. [19] Roberto De Prisco, Dahlia Malkhi, and Michael K. Reiter. On k-set consensus problems in asynchronous systems. In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’99, 1999. [20] Danny Dolev, Michael J Fischer, Rob Fowler, Nancy A Lynch, and H Raymond Strong. An efficient algorithm for byzantine agreement without authentication. Information and Control, 52(3):257–274, 1982. 34

[21] Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33(3):499–516, May 1986. [22] El-Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyên Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, 2021. [23] Matthias Fitzi and Juan A. Garay. Efficient player-optimal protocols for strong and differential consensus. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, PODC ’03, page 211–220, 2003. [24] Matthias Függer and Thomas Nowak. Fast Multidimensional Asymptotic and Approximate Consensus. In Ulrich Schmid and Josef 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. [25] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, pages 141–151, 2023. [26] Diana Ghinea, Darya Melnyk, and Tijana Milentijević. Network-agnostic multidimensional approximate agreement with optimal resilience. In ACM Symposium on Principles of Distributed Computing, pages 527–538, 2026. [27] Diana-Elena Ghinea. Convex Validity. PhD thesis, ETH Zurich, 2025. [28] Sang-Sub Kim and Barbara Schwarzwald. A (1+ ε)-approximation for the minimum enclosing ball problem in r d. In the 36th European Workshop on Computational Geometry (EuroCG), 2020. [29] Piyush Kumar, Joseph S. B. Mitchell, and E. Alper Yildirim. Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Exp. Algorithmics, 8:1.1–es, December 2004. [30] Christoph Lenzen and Julian Loss. Optimal clock synchronization with signatures. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 440–449, 2022. [31] Nancy A Lynch. Distributed algorithms. Elsevier, 1996. [32] Darya Melnyk. Faster convergence of multidimensional approximate agreement via smallest enclosing balls, 2026. [33] Darya Melnyk and Roger Wattenhofer. Byzantine agreement with interval validity. In 2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS), 2018. [34] Hammurabi Mendes and Maurice Herlihy. Multidimensional Approximate Agreement in Byzantine Asynchronous Systems. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC, 2013. [35] Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K Garg. Multidimensional agreement in byzantine systems. Distributed Computing, 28(6):423–441, 2015. 35

[36] M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, April 1980. [37] Hin-Sing Siu, Yeh-Hao Chin, and Wei-Pang Yang. Reaching strong consensus in the presence of mixed failure types. Information Sciences, 108(1):157–180, 1998. [38] TK Srikanth and Sam Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80–94, 1987. [39] David Stolz and Roger Wattenhofer. Byzantine Agreement with Median Validity. In 19th International Conference on Priniciples of Distributed Systems, OPODIS, 2015. [40] Lili Su and Nitin H Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In Proceedings of the 2016 ACM symposium on principles of distributed computing, pages 425–434, 2016. [41] Nitin H. Vaidya and Vijay K. Garg. Byzantine Vector Consensus in Complete Graphs. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC, 2013. [42] Lieven Vandenberghe and Stephen Boyd. Convex optimization, volume 1. Cambridge university press Cambridge, 2004. [43] Zhuolun Xiang and Nitin H. Vaidya. Relaxed Byzantine Vector Consensus. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:15, 2017.

Record · ID 667989 · SHA-256 3d2a2e2763f28cc6
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.