A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities

摘要

The distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg devised an algorithm with running time O(D +n~(1/2)·log* n), where D is the hop diameter of the input n-vertex m-edge graph, and with message complexity O(m + n~(3/2)). Peleg and Rubinovich showed that the running time of the algorithm of Kutten and Peleg is essentially tight and asked if one can achieve near-optimal running time together with near-optimal message complexity.In a recent breakthrough, Pandurangan et al. answered this question in the affirmative and devised a randomized algorithm with time O(D + n~(1/2)) and message complexity O(m). They asked if such a simultaneous time- and message optimality can be achieved by a deterministic algorithm.In this article, building on the work of Pandurangan et al., we answer this question in the affirmative and devise a deterministic algorithm that computes MST in time O((D + n~(1/2))·log n) using O(m·log n + n log n· log* n) messages. The polylogarithmic factors in the time and message complexities of our algorithm are significantly smaller than the respective factors in the result of Pandurangan et al. In addition, our algorithm and its analysis are very simple and self-contained as opposed to rather complicated previous sublinear-time algorithms.Finally, we use our new algorithm to devise a randomized MST algorithm with running time O(μ(G, ω) + n~(1/2)) and message complexity O(|E|), where μ-radius μ(G,ω) ≤ D is a graph parameter, which is typically much smaller than D. This improves a previous bound from Elkin.