Fast Multidimensional Approximate Agreement with Optimal Resilience Using Ball Validity

1 Introduction

• Convex validity requires n>(d+1)t synchronously and n>(d+2)t asynchronously, limiting fault tolerance as dimension grows.The paper asks whether dimension-free resilience can be achieved while preserving constant geometric validity.Source: §1 · p. 2

1.2 Technical Overview

• Directly contracting the correct MEB radius makes the contraction factor independent of dimension, while nested enlarged MEBs account for center drift in the validity proof.The nested-ball argument yields validity relative to the initial correct MEB in every round.Source: §1 · p. 2, §1.2 · p. 5

1.1 Our Contributions

• At α=1, synchronous Adaptive MEB Contraction shrinks the correct-values’ MEB radius by 1/√2 per round while satisfying √2-MEB validity.The paper says this contraction bound is tight for its analysis.Source: §1.1 · p. 2
• Ball inflation extends the approach to optimal synchronous resilience n>3t, with constant √6-MEB validity.The dimension-free theorem guarantees a common intersection after inflating balls when every β balls already intersect.Source: §1.1 · p. 3

1.2 Technical Overview

• In the asynchronous setting, without inflation, the approach yields an algorithm for n > (d + 2)t; with inflation, it yields a dimension-free algorithm for n > 4t.Source: §1.1 · p. 3
• The paper derives MEB-validity guarantees for MDA and reports stronger validity guarantees at better resilience thresholds for its own algorithms.MDA is reported to satisfy 7-MEB validity synchronously and 11-MEB validity asynchronously; the paper’s inflated algorithms are reported to have strictly better resilience thresholds.Source: §1.2 · p. 6

Approximate agreement

• Convex validity has optimal resilience thresholds n > (d + 1)t synchronously and n > (d + 2)t asynchronously [41].Multidimensional approximate agreement and these thresholds were studied by Mendes, Herlihy, Vaidya, and Garg [41].Source: §2 · p. 6

Validity conditions and relaxations

• Relaxed convex, projected, and coordinate-wise box validity offer alternatives, while box validity remains tied to coordinate choice.Xiang et al. study lower-dimensional projections and (δ, p)-relaxed validity.Source: §2 · p. 7

Minimum enclosing balls and MEB validity

• MEB validity was introduced for vector consensus, and this work adapts it to iterative approximate agreement, where validity must persist across rounds.Concurrent work applies MEBs to contraction within the convex safe area.Source: §2 · p. 7

Core-sets and algorithms for minimum enclosing balls

• Adaptive MEB Contraction adapts the core-set idea of repeatedly adding farthest points, selecting them from the continuous MEB-safe area instead.Related approaches include other core-set constructions and gradient-type methods.Source: §2 · p. 7

Communication primitives

• The synchronous model uses consistent broadcast, while the asynchronous model uses Gather [2].Consistent broadcast guarantees consistency among values delivered by correct processes; unlike reliable broadcast, it need not deliver a faulty sender's value to every correct process.Source: §2 · p. 7

Correct and faulty processes

• At most t of n processes are Byzantine; they may collaborate, know all inputs and the algorithm, and send arbitrary values or omit messages.Correct processes do not know which processes are faulty or how many are faulty beyond the upper bound t.Source: §3 · p. 7

Communication

• Synchronous rounds use consistent broadcast, while asynchronous local views come from Gather, whose common-core includes values from at least n − t senders.The common-core is contained in every correct process's local view.Source: §3 · p. 8

Multidimensional approximate agreement

• Approximate agreement requires correct outputs to become close, satisfy validity relative to correct inputs, and terminate in finite time.The model measures closeness using Euclidean distance.Source: §3 · pp. 8–9

Convex validity

• For multidimensional approximate agreement, convex validity requires an algorithm to output a vector inside the convex hull of correct processes.The paper considers dimensions d ≥ 2.Source: §3 · pp. 8–9

MEB validity

• MEB validity requires outputs inside the correct inputs' minimum enclosing ball; c-MEB validity allows distance up to c times its radius from its center.The MEB is unique, and convex validity implies 1-MEB validity; relaxing the MEB radius is proposed to improve resilience.Source: §3 · p. 9

MEB-safe area

• The MEB-safe area is the intersection of minimum enclosing balls over subsets of size n − t, and c-SafeMEB inflates each such ball's radius by c.MEB validity requires agreement inside the intersection of these candidate MEBs.Source: §3 · p. 9

Adaptive MEB Contraction

• Each process adds the farthest point from its current minimax center until all safe-area points lie within α times the selected-set radius.The selected set represents the safe area, and the process outputs the center when the stopping criterion is met.Source: §4 · p. 10
• For α = 1, the output is the center of the minimum enclosing ball of the entire MEB-safe area.Intermediate α values interpolate between this case and stopping once the center approximates the area within the chosen factor.Source: §4 · p. 11

Contraction analysis

• Smaller α strengthens contraction but requires the selected support set to represent the MEB-safe area more accurately.The parameter α trades off computational effort and contraction quality.Source: §4 · p. 12
• 1/√2 is the contraction factor for α = 1 when n > (d + 1)t, with √2-MEB validity.The contraction rate is independent of dimension.Source: §4 · pp. 11, 13
• An α = 1 example attains the 1/√2 contraction factor, showing the bound is tight for the analysis.The paper contrasts this dimension-independent bound with MidExtremes' 7/8 ≈ 0.935 bound, while noting that the models differ.Source: §4 · p. 13

5.1 Resilience n > (d + 1)t

• For n > (d + 1)t, Adaptive MEB Contraction solves synchronous approximate agreement with (1 + α²)-MEB validity; at α = 1, contraction is 1/sqrt(2) and validity is sqrt(2).All locally computed MEB-safe areas intersect under this resilience condition.Source: §5.1 · pp. 13, 15

5.2 Ball Inflation Analysis

• When n > 3t, candidate MEBs need not intersect, so inflating their radii by a factor ensures a common point for the safe-area construction.The section applies the inflation bound to candidate balls in the optimal-resilience setting.Source: §5.2 · pp. 15–16
• Inflating each ball by sqrt(β/(β − 1)) guarantees a common intersection when every subfamily of at most β balls already intersects.The bound is multiplicative in each ball’s radius; the proof finds at most β active balls with approximately balanced directions and uses their pre-inflation common point.Source: §5.2 · pp. 16, 18

5.3 Multidimensional Approximate Agreement with Optimal Resilience n > 3t

• The algorithm inflates candidate MEBs of subsets of size at least n−t; when n>3t, every three candidate balls intersect, enabling common safe areas.Any three candidate subsets exclude at most 3t processes, so they share a process whose consistently broadcast value lies in all three MEBs; inflation then ensures a common intersection.Source: §5.3 · pp. 19–20
• The contraction analysis permits 1≤α<sqrtβ−1, and both contraction rate and validity improve as α decreases.For n>3t, β≥3, so α=1 is admissible and the upper bound is at least sqrt2.Source: §5.3 · pp. 20, 22
• With n>3t and α=1, the inflated algorithm achieves contraction sqrt3/2 and sqrt6-MEB validity.The result applies to synchronous multidimensional approximate agreement.Source: §5.3 · pp. 19, 21, 22

6 Asynchronous Approximate Agreement

• Gather returns a common-core of at least n - t values, but processes may not know which values belong to it and may hold different local views.Because correct messages can be arbitrarily delayed, processes cannot safely wait for all correct values before proceeding.Source: §6 · p. 22, §6.1 · p. 23

6.1 Asynchronous Algorithm

• Processes form candidate subsets relative to each local view, removing only t values so views retain more of the common-core and avoid a stronger resilience requirement.Fixing every subset to size n - 2t would discard additional values from larger views and weaken the intersection guarantee.Source: §6.1 · p. 23

6.2 Resilience n > (d + 2)t

• At n > (d + 2)t, asynchronous Adaptive MEB Contraction achieves dimension-independent sqrt(2/3) radius contraction and sqrt6-MEB validity.The contraction applies per round; the algorithm solves multidimensional approximate agreement under this resilience condition.Source: §6.2 · p. 25

6.3 Multidimensional Approximate Agreement with Resilience n > 4t

• For dimension-free resilience n > 4t, the approach inflates candidate-ball radii and enlarges candidate subsets; the Gather counting argument ensures every three candidate balls intersect.This applies the inflation theorem with β = 3; the larger subsets also support relating the inflated safe area to the MEB of locally received correct values.Source: §6.2 · p. 26, §6.3 · p. 27
• Inflating candidate-ball radii by √(β/(β−1)) guarantees a common point in all candidate balls when every β of them intersect.For n > 4t, the proof applies this result with β = 3 and inflation factor 3/2 to obtain a point in every correct process’s inflated safe area.Source: §6.3 · p. 27
• In the asynchronous setting with n > 4t, Theorem 6.6 states that the Inflated Asynchronous Adaptive MEB Contraction Algorithm solves multidimensional approximate agreement.Source: §6.3 · p. 29
• As n/t grows, β increases and λ approaches one, broadening the admissible α range; for n > 4t, α can be chosen only slightly above one.The stated bound for n > 4t is λ ≤ √(10/9) ≈ 1.054.Source: §6.3 · p. 29
• Even at λ = 1, the asynchronous admissible range remains α < √2, a restriction imposed by the Gather protocol rather than ball inflation.For n > 4t, the range is narrow, while increasing n/t broadens it.Source: §6.3 · pp. 29–30

Tightness example

• In the n = 7, t = 2, d = 2 example, local views differ by which Byzantine point they include, producing symmetric safe areas.The example uses Byzantine values (1, 1) and (−1, −1) alongside five correct values.Source: §7 · p. 30
• The α = 1 contraction factor 1/√2 is attained by the example, so it is tight for this geometric analysis.The authors state that this factor cannot be improved within their contraction analysis.Source: §7 · p. 30

Comparison with Minimum-Diameter Averaging

• MDA’s synchronous and asynchronous bounds are 7-MEB and 11-MEB validity, derived by summing drift while using its diameter-contraction bounds.The proof bounds each round’s drift by the correct-value diameter, then applies geometric-series bounds.Source: §7 · pp. 31–32
• The synchronous algorithm achieves n > 3t resilience with 6-MEB validity, versus MDA’s n > 4t and 7-MEB validity; asynchronously, the comparison is n > 4t and 2√10-MEB versus n > 7t and 11-MEB.The authors report that their bounds provide better resilience and MEB-validity guarantees than MDA in both settings.Source: §7 · p. 32

Computational aspects

• The parameter α trades local computation against round complexity: smaller α improves contraction but may require more farthest-point queries.For α = 3, the initial diameter pair already satisfies the stopping criterion, so no additional queries are needed.Source: §7 · p. 32
• Inflated variants intersect MEBs over larger families of candidate subsets, which can make direct implementation substantially more expensive.Efficient implementations and approximation routines for inflated MEB-safe areas remain future work.Source: §7 · p. 33

• ChatGPT and Claude assisted with presentation and clarity; the authors state that they originated and verified the technical results, definitions, algorithms, proofs, and references.Source: AI Disclosure · p. 33