Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel distributed algorithm for constructing a minimum spanning tree (MST) in the \textsf{CONGEST-KT$_{1}$} model, achieving a significant improvement in the time-message trade-off. By exposing a two-parameter trade-off, the algorithm operates in $\tilde{O}(n^{1/2} + n^{1/6}D_G)$ rounds while utilizing only $\tilde{O}(n^{4/3})$ messages, surpassing the previous best message bound of $\tilde{O}(n^{3/2})$. This breakthrough effectively breaks the quadratic time-message trade-off barrier, which has hindered MST algorithms in this model, and also yields new algorithms for low-message broadcast, spanning-tree, and leader-election tasks.
Breaking the quadratic time-message trade-off barrier in distributed MST construction could revolutionize network algorithms in constrained environments.
We present a new distributed algorithm for computing a minimum spanning tree (MST) in the \textsf{CONGEST-KT$_{1}$} model, where messages are limited to $O(\log n)$ bits and each vertex initially knows the identifiers of its neighbors. Our algorithm exposes a two-parameter time--message trade-off: for any $0 \leq λ\leq κ\leq 1/2$, it runs in $\tilde{O}(n^λD_G + n^{1 - κ- λ} + n^{1 - 2κ+ λ} + n^{1/2})$ rounds and uses $\tilde{O}(\min\{m, n^{1 + κ}\})$ messages, where $n$, $m$, and $D_G$ are the number of vertices, edges, and thenetwork diameter, respectively. In particular, setting $(κ, λ) = (1/3, 1/6)$ yields an MST algorithm running in $\tilde{O}(n^{1/2} + n^{1/6}D_G)$ rounds with only $\tilde{O}(n^{4/3})$ messages. Under the mild assumption $D_G = O(n^{1/3})$, this is round-optimal while improving the best known message bound of $\tilde{O}(n^{3/2})$. More broadly, our algorithm breaks the quadratic time--message trade-off barrier $\mathrm{\# rounds} \cdot \mathrm{\# messages} = \tildeΩ(n^2)$, which no previous MST algorithm in the \textsf{CONGEST-KT$_{1}$} model has been able to overcome, and it does so for almost the entire range of the diameter $D_G$. As a byproduct, we also obtain new low-message broadcast, spanning-tree, and leader-election algorithms.