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

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\le \lambda \le \kappa \le 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 $\#rounds\cdot \#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.