Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

ABSTRACT

This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. Those problems include Minimum-Weight Spanning Tree (MST), Leader Election, counting the number of network nodes, and computing a sensitive decomposable function (e.g. majority, parity, maximum, OR, AND). The main problem considered is the problem of finding the MST. This problem, which has been known for at least 9 years, is one of the most fundamental and the most studied problems in the field of distributed network algorithms. Any algorithm for any one of the problems above requires at least &OHgr;(E + VlogV) communication and &OHgr;(V) time in the general network. In this paper, we present new algorithms, which achieve those lower bounds. The best previous algorithm requires &THgr;(E + VlogV) in communication and &THgr;(V log V) in time. Our result enables to improve algorithms for many other problems in distributed computing, achieving lower bounds on their communication and time complexities.

REFERENCES

• A-85: 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]
• AD-76: Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
• Afek-85: Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323613]
• AE-86: B. Awerbuch and S. Even, Reliable Broadest in Unreliable Networks, to appear in Networks.
• AG-85: B.Awerbuch and R.Gallager, "Distributed Breadth-FirsbSearch Algorithms", IEEE Symposium on Foundation8 of Computer Science, October 1985, Portland, Oregon.
• AGV-87: B.Awerbuch, O.Goldreich and R.Vainish, "On message complexity of broadcast: a bamc lower bound", unpublished manuscript, January 1987.
• AM-85: B. Awerbueh and S.Micali, "Dynamic Deadlock Resolution Protocols with Bounded Complexities", uapublished manuscript, MIT, 1985.
• AM-86: B. Awerbuch and $.Micali, "Dynamic Deadlock Resolution Protocols", Proceedings o/~1986 FOOS Conference, Toronto, Ontario, October 1986.
• AP-86: B.Awerbuch and S.P!otkin, "A.n O(E+ Vlog2V) leader election in faulty networks", unp'ublished manuscript, MIT, December 1986.
• B-80: J.E.Burns, "A Formal Model for Message-Passing Systems", TR-91, indiana Univ., Bloomington, May 1980.
• CT-85: F.Ch. in and H.F.Ting, "An almost linear time and O(l/log V+E) messages Distributed Algorithm for Minimum Weight Spanning Trees", Proce~'ding, of 1985 FOGS Conference, Portland, Oregon, October 1985.
• DM-78: Yogen K. Dalal , Robert M. Metcalfe, Reverse path forwarding of broadcast packets, Communications of the ACM, v.21 n.12, p.1040-1048, Dec. 1978 [doi>10.1145/359657.359665]
• FL-84: Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984 [doi>10.1145/800057.808719]
• G-85: 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]
• GHS-83: 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]
• K-78: P. Kmaellakis, "An Election Problem in a Network", #.854 term paper, MIT, May 1978.
• KMZ-84: E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806747]
• MMP-78: Daniel A. Menasce , Gerald J. Popek , Richard R. Muntz, A locking protocol for resource coordination in distributed databases, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509256]
• S-77: P.Spira, "Communication Complexity of distributed minimum spanning tree algorithms", ~nd Berkele~l Conferenee on Distributed Data Management and Computer Networks, Berkeley, California, June 1977.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Trees

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Theory, Verification