Source-linked AI summary
New Contraction Bounds for Multidimensional Asymptotic Consensus in Dynamic Networks
Zeremonienmeister Berber Aab, Darya Melnyk, Stefan Schmid
TL;DR
The paper studies multidimensional asymptotic agreement in dynamic non-split networks. It presents a coordinate-free, memoryless, anonymous protocol and analyzes its contraction alongside lower bounds. The results include an upper bound for the protocol and lower bounds for general and one-round contraction.
Problem
The paper studies how multidimensional node values can converge in dynamic networks while addressing contraction in the non-split model.
Source: §1 · pp. 1–2, §3 · p. 6Method
It presents a coordinate-free, memoryless, anonymous protocol and analyzes its contraction in non-split networks.
Source: §1 · p. 2, §3 · pp. 5–6Results
The paper establishes a contraction upper bound for its protocol, lower bounds for finite and infinite node settings, and an asymptotically tight one-round bound.
Source: §6 · pp. 17–18Takeaways & Limitations
The algorithm's contraction analysis is asymptotically tight for one round, but the reported multi-round lower bounds do not make the algorithm tight.
Source: §6 · p. 18The multi-round bounds are not tight, and the authors identify constructing a self-similar example from the one-round lower bound as difficult.
Source: §6 · p. 18
Abstract
from arXiv · showhide
This work studies the multidimensional asymptotic agreement problem in dynamic networks. We assume that nodes have $d$-dimensional inputs and need to converge arbitrarily close to each other's inputs while their vectors stay inside the convex hull of all inputs. We present a new upper bound of $\sqrt{2d/(3d+1)}$ on the contraction rate of asymptotic agreement in the non-split network model, where $d$ is the dimension of the input and $\sqrt{2d/(3d+1)}\rightarrow \sqrt{2/3}\approx 0.816$ for $d\rightarrow\infty$. To this end, we adapt the BallMidpoint algorithm (Melnyk, 2026) recently introduced for the all-to-all communication model. This algorithm lets the nodes choose the midpoint of the smallest enclosing ball of the received vectors. This bound is strictly worse than the $\sqrt{1/2}\approx 0.707$ contraction rate for fault-tolerant approximate agreement in all-to-all communication networks because the convex hulls of the nodes do not have a common intersection, and only intersect pairwise. Our bound improves over the previously best-known contraction rate of $\sqrt{7/8}\approx 0.935$ for dynamic networks via the MidExtremes algorithm (F\"ugger and Nowak, 2018). We present the first multi-dimensional lower bound of $2/3$ for the contraction of coordinate-free memoryless anonymous deterministic algorithms in non-split networks, for $d\ge 8$. This result shows that the previously best-known lower bound of $1/2$ on the contraction rate for $n\ge 3$ and $d=1$ is not tight in higher dimensions. If $n$ is infinite, we extend this lower bound to $\sqrt{1/2\cdot d/(d+1)}$, which converges to $\sqrt{1/2}$ for $d\rightarrow \infty$. We further show that for a single round, the one-round contraction is at least $\sqrt{\frac{2d-2}{3d+7}}$, which converges to $\sqrt{2/3}$ for $d\rightarrow\infty$, showing that the BallMidpoint strategy is asymptotically optimal for one round.
1 Introduction
The introduction frames multidimensional asymptotic agreement as useful when exact agreement is impossible or costly, and presents a contraction analysis and lower bounds for dynamic networks. Its contributions adapt BallMidpoint to non-split networks and establish bounds for general and one-round contraction.
Motivation
- Asymptotic agreement covers approximate agreement and averaging agreement, which model robot gathering and collaborative learning, respectively [32] [7].In robot gathering, nodes may stop once their locations are close; collaborative learning may use a constant number of updates to limit model divergence.Source: §1 · p. 1
Related work
Contributions
- The paper adapts BallMidpoint, which selects the midpoint of a smallest enclosing ball, to dynamic networks where locally received convex hulls need not share a common intersection.The non-split model instead guarantees that convex hulls of any two received views intersect; the paper focuses its contraction analysis on this model.Source: §1 · p. 2
- The paper presents a coordinate-free, memoryless, anonymous protocol with a contraction upper bound for dynamic non-split networks.The introduction says its contraction analysis is tight for one round; it also reports that the strategy converges in rooted tree networks but is not memoryless there.Source: §1 · p. 2
- The paper establishes a contraction lower bound of 2/3 for coordinate-free, memoryless, anonymous algorithms when d ≥ 8 and the network has at least 241 nodes.Source: §1 · p. 2
- For one communication round, the contraction lower bound approaches 2/3 as d grows, making the presented algorithm's one-round analysis asymptotically tight.The construction uses products of two regular simplices with d symmetry axes, forcing the centroid as the only choice for coordinate-free, memoryless, anonymous algorithms.Source: §1 · p. 3
- Regular d-simplex symmetry underlies the multi-round lower-bound constructions, while MidExtremes may require tie-breaking incompatible with deterministic, anonymous, coordinate-free operation.The simplex symmetry leaves the centroid as the only eligible next-round point; the introduction notes that tie-breaking for an equilateral triangle requires a coordinate system, IDs, or randomization.Source: §1 · p. 3
2 Related Work
Prior work extends approximate agreement to multiple dimensions and studies contraction in dynamic networks. The paper builds on earlier dynamic-network algorithms and lower bounds, while adapting a strategy previously analyzed for static all-to-all communication.
Asymptotic and approximate agreement
- Multidimensional approximate agreement asks nodes to converge inside the convex hull of the non-faulty inputs, extending one-dimensional approximate agreement.Related work considers this problem across communication models, domains, applications, and relaxed validity conditions.Source: §2 · pp. 3–4
Dynamic networks and contractions
- In multidimensional dynamic networks, the Centroid algorithm achieves contraction d/(d + 1) [11], while MidExtremes improves the bound to 7/8.ApproachExtreme offers faster local computation at the cost of worse contraction.Source: §2 · p. 4
- BallMidpoint achieves contraction 1/2 for static all-to-all communication, but its analysis assumes all received convex hulls share a common intersection [29].That intersection cannot be guaranteed in dynamic networks, motivating this paper's adaptation.Source: §2 · p. 4
Lower bounds on contractions
- For dynamic networks, prior lower bounds include 1/2 for non-split networks when n ≥3 and d = 1.The paper presents the first multidimensional lower bounds for non-split graphs that improve on this one-dimensional bound.Source: §2 · p. 4
3 Model and Definitions
The model uses adversarial, changing communication graphs and deterministic, memoryless, anonymous, coordinate-free updates. Agreement requires convergence to a shared limit within the convex hull of initial states, and contraction measures shrinkage of the smallest enclosing ball.
Model
- The network is finite, synchronous, and adversarial: communication graphs may change each round, with rooted-tree and non-split models considered.The paper also considers countably infinite nodes in Section 5.2.Source: §3 · pp. 4–5
- Algorithms are deterministic, memoryless, anonymous, and coordinate-free; each node's transition function takes the multiset of received values as input.Coordinate-free means equivariant under translations, scalings, and orthogonal linear maps.Source: §3 · pp. 4–5
Asymptotic agreement
- Asymptotic agreement requires every node's state sequence to converge, all nodes to share the same limit, and that limit to lie in the convex hull of initial states.Source: §3 · pp. 5–6
Execution
- Each round, a node applies its transition function to the multiset of states in its closed in-neighborhood, including its own state.Source: §3 · pp. 5–6
Contraction
- The smallest enclosing ball is the minimum-radius ball containing a point set, and one-round contraction is the ratio of output-set to input-set radii.When all input states coincide, the defined contraction is zero.Source: §3 · p. 6
- The contraction rate takes the worst case over instances; in non-split networks, any two local views' convex hulls intersect, while rooted-tree reduction to non-split networks requires n −1 rounds and is not memoryless.Source: §3 · p. 6
4 Asymptotic Agreement Algorithm
BallMidpoint selects the circumcenter of the smallest enclosing ball of received values. The paper proves an upper bound for its contraction in non-split networks, shows that the analysis is tight for one round, and establishes convergence in rooted-tree networks.
4 Asymptotic Agreement Algorithm
- BallMidpoint maps each received multiset to the circumcenter of its smallest enclosing ball, a choice that is coordinate-free.Source: §4 · p. 7
4.1 Contraction of BallMidpoint in non-split networks
- BallMidpoint solves asymptotic agreement in non-split networks with the contraction upper bound stated in Theorem 1.The proof places each output in its received convex hull and shows that the nested hulls shrink to a unique valid common limit.Source: §4.1 · pp. 7, 9
4.2 Tightness of the contraction analysis for one round
- The contraction analysis is tight for one round in every dimension, using a non-split construction whose nodes' received sets are pairwise intersecting.Theorem 2 states a one-round instance for d ≥2.Source: §4.2 · p. 9
4.3 BallMidpoint in rooted tree networks
- BallMidpoint solves asymptotic agreement in rooted-tree networks by applying the algorithm after each n −1-round macro-round reduction to a non-split graph [10].Source: §4.3 · p. 10
5 Lower Bounds on Contraction in Non-Split Networks
The section establishes contraction lower bounds in non-split networks across finite and infinitely large settings, including finite-round and single-round cases. The one-round lower bound approaches √(2/3) as the dimension grows.
5 Lower Bounds on Contraction in Non-Split Networks
- Symmetric input sets force algorithms to choose their unique fixed point, enabling constructions that reproduce the configuration up to rotation and scaling each round.The section identifies hypercubes, regular simplices, and regular polytopes as examples with sufficient symmetry to force selection of the barycenter or center of mass.Source: §5 · p. 10
- The one-round contraction lower bound converges to 2/3 as d grows, making BallMidpoint asymptotically optimal for one round.The section also states that this construction can be achieved with finitely many nodes when the algorithm has a fixed number of rounds.Source: §5 · p. 10
5.1 Lower bound for d ≥8
- In the non-split communication model, every coordinate-free memoryless anonymous deterministic asymptotic agreement algorithm in dimension d ≥ 8 with n ≥ 241 nodes has contraction rate lower bound 2/3.Source: §5.1 · pp. 12–13
5.2 Lower bound for |N| = ∞
- For every transition function, when d ≥ 3 and countably infinitely many nodes are allowed, the theorem guarantees an instance whose contraction rate has a lower bound.The construction uses locally finite graphs and does not require the axiom of choice.Source: §5.2 · pp. 13, 15
- The cited passage reports a construction for every positive integer r, but its displayed fragment does not provide a readable bound in d or identify a contraction lower bound.Source: §5.2 · p. 15
- For d ≥ 3, any transition function, and any positive round count R, a finite-node network instance exists with a contraction lower bound; its required node count grows exponentially in R.Source: §5.2 · pp. 15–16
5.3 One-round lower bound
- For d ≥ 3, every transition function has a non-split instance whose one-round contraction is at least √((2d−2)/(3d+7)), approaching √(2/3) as d grows.The construction uses node groups that receive sets of states with centroids at the group update points.Source: §5.3 · p. 17
6 Conclusion
The paper analyzes BallMidpoint in non-split and rooted-tree networks, improving the non-split contraction bound and giving lower bounds for restricted algorithms. Its one-round analysis is asymptotically tight, while the broader bounds remain untight.
6 Conclusion
- The paper also analyzes BallMidpoint in rooted-tree networks.Source: §6 · p. 17
- The non-split contraction rate is bounded by 2d/(3d + 1), improving on MidExtremes’ 7/8 bound.The paper analyzes BallMidpoint in the non-split model.Source: §6 · p. 17
- Approximate agreement requires a round counter, an initial-radius upper bound, and ε; the counter means the algorithm is no longer memoryless.Source: §6 · pp. 17–18
- A constructive 2/3 lower bound applies to coordinate-free memoryless anonymous algorithms in non-split networks.Source: §6 · p. 18
- The one-round lower bound is asymptotically matched by the algorithm, but the broader lower bounds are not tight.The authors identify constructing a self-similar example from the one-round bound as a difficulty and suggest amortized analysis of BallMidpoint for future work.Source: §6 · p. 18