Beating Quadratic Time--Message Trade-off in Distributed Minimum Spanning Tree Construction
TL;DR
A new distributed algorithm for computing a minimum spanning tree (MST) in the CONGEST-KT model, where messages are limited to $O(\log n)$ bits and each vertex initially knows the identifiers of its neighbors, which breaks the quadratic time--message trade-off barrier.
Abstract
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 \lambda \leq \kappa \leq 1/2$, it runs in $\tilde{O}(n^{\lambda}D_G + n^{1 - \kappa - \lambda} + n^{1 - 2\kappa + \lambda} + n^{1/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/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{\Omega}(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.