Beating Quadratic Time--Message Trade-off in Distributed Minimum Spanning Tree Construction

We present a new distributed algorithm for computing a minimum spanning tree (MST) in the $\mathsf{\text{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\le \lambda \le \kappa \le 1\mathrm{/}2$, it runs in $\tilde{O}(n^{\lambda }{D}_G+n^{1-\kappa -\lambda }+n^{1-2\kappa +\lambda }+n^{1\mathrm{/}2})$ rounds and uses $\tilde{O}(\min \{m,n^{1+\kappa }\})$ messages, where $n$, $m$, and $D_G$ are the number of vertices, edges, and thenetwork diameter, respectively. In particular, setting $(\kappa ,\lambda )=(1\mathrm{/}3,1\mathrm{/}6)$ yields an MST algorithm running in $\tilde{O}(n^{1\mathrm{/}2}+n^{1\mathrm{/}6}{D}_G)$ rounds with only $\tilde{O}(n^{4\mathrm{/}3})$ messages. Under the mild assumption $D_G=O(n^{1\mathrm{/}3})$, this is round-optimal while improving the best known message bound of $\tilde{O}(n^{3\mathrm{/}2})$. More broadly, our algorithm breaks the quadratic time–message trade-off barrier $\mathrm{\#}\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{s}\cdot \mathrm{\#}\mathrm{m}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{a}\mathrm{g}\mathrm{e}\mathrm{s}=\tilde{\mathrm{\Omega }}(n^2)$, which no previous MST algorithm in the $\mathsf{\text{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.