Improved bounds on consensus speeds for vectors in dynamic networks
New Contraction Bounds for Multidimensional Asymptotic Consensus in Dynamic Networks
Distributed, Parallel, and Cluster Computing
Summary
In networks where many devices or nodes try to agree on a shared value represented by multiple numbers, it’s challenging to reach agreement quickly and reliably. The paper studies how fast nodes can come close to each other’s values when those values are multi-dimensional vectors. The authors found a new tighter upper limit on how quickly agreement can improve under certain network conditions, and they also proved new lower limits showing how fast any method can possibly be. Their results help explain the best possible speed of consensus in complex network settings.
What this means in practice
- •For distributed system designers: Design algorithms for reliable consensus in systems where network connections change dynamically and data inputs have multiple dimensions.
- •For network protocol developers: Develop protocols that guarantee faster convergence to approximate agreement in networks with unstable or partial communication links.
A theory result. No direct application yet.
Authors
Zeremonienmeister Berber Aab, Darya Melnyk, Stefan Schmid
Abstract
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ügger 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.