A faster distributed protocol for constructing a minimum spanning tree

ABSTRACT

This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time O(∧(G) + √n log* n) due to Kutten and Peleg [KP95], where ∧(G) denotes the diameter of the graph G. Peleg and Rubinovich [PR99] have shown that (√n) time is required for constructing MST even on graphs of small diameter, and claimed that their result "establishes the asymptotic near-optimality" of the protocol of [KP95].In this paper we refine this claim, and devise a protocol that constructs the MST in Õ(μ(G = w + √n) rounds, where μ(G,μ) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [KP95] by a factor of (√n). Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [KP95].As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.

REFERENCES

• 1: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 2: B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
• 3: B. Awerbuch, Randomized distributed shortest paths algorithms, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.490-500, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73054]
• 4: {ABCP93} B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Near-linear cost sequential and distributed constructions of sparse neighborhood covers. In Proc. Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 638--647, 1993.
• 5: Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Fast distributed network decompositions and covers, Journal of Parallel and Distributed Computing, v.39 n.2, p.105-114, Dec. 15, 1996 [doi>10.1006/jpdc.1996.0159]
• 6: Baruch Awerbuch , Robert G. Gallager, A new distributed algorithm to find breadth first search trees, IEEE Transactions on Information Theory, v.33 n.3, p.315-322, May 1, 1987 [doi>10.1109/TIT.1987.1057314]
• 7: {AGLP89} B. Awerbuch, A. Goldberg, M. Luby and S. Plotkin, Network decomposition and locality in distributed computation. in Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364--369, 1989.
• 8: {AP90a} B. Awerbuch and D. Peleg, Network synchronization with polylogarithmic overhead. In 31st IEEE Symp. on Foundations of Computer Science, pp. 514--522, Oct. 1990.
• 9: {AP90b} B. Awerbuch and D. Peleg, Efficient distributed construction of sparse covers. Technical Report CS90-17, The Weizmann Institute of Science, Rehovot, Israel, July 1990.
• 10: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 11: {AS92} N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1992, p.239.
• 12: {CT85} F. Chin and H.F. Ting, An almost linear time and O(n log n + e) messages distributed algorithm for minimum-weight spanning trees, in Proc. 26th IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA, 1985, pp.257--266.
• 13: {Coh93} E. Cohen, Fast Algorithms for constructing t-spanners and paths of stretch t, in Proc. 34th IEEE Symp. on Foundations of Computer Science, IEEE, Piscataway, NJ, 1993, 648--658.
• 14: Cynthia Dwork , Yoram Moses, Knowledge and common knowledge in a byzantine environment: crash failures, Information and Computation, v.88 n.2, p.156-186, Oct. 1990 [doi>10.1016/0890-5401(90)90014-9]
• 15: Michael Elkin, Computing almost shortest paths, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.53-62, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383983]
• 16: {Elk03} M. L. Elkin, Unconditional Lower Bounds on the Time-Approximation Tradeoff for the Distributed Minimum Spanning Tree Problem, manuscript, 2003.
• 17: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 18: Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323612]
• 19: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 20: {GKP93} J.A. Garay, S. Kutten and D. Peleg, A sublinear time distributed algorithm for minimum-weight spanning trees, in Proc. of 34th IEEE Symp. on Foundations of Computer Science, Palo Alto, CA, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 659--668.
• 21: Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224990]
• 22: {Lev72} L. A. Levin, Universal Search Problems, in Problemy Peredaci Informacii 9, pp. 115--116, 1973. Translated in problems of Information Transmission 9, pp. 265--266.
• 23: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 24: Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
• 25: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 26: {Pe100a} "-----", pp.273--275.
• 27: David Peleg , Vitaly Rubinovich, A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.253, October 17-18, 1999