Randomized distributed shortest paths algorithms

ABSTRACT

This paper is concerned with distributed algorithm for finding shortest paths in an asynchronous communication network. For the problem of Breadth First Search, the best previously known algorithms required either &THgr;(V) time, or &THgr; (E + V · D) communication. We present new algorithm, which requires O(D1+&egr;) time, and O(E1+&egr;) messages, for any &egr; > 0. (Here, V is number of nodes, E is number of edges and D is the diameter.) This constitutes a major step towards achieving the lower bounds, which are &OHgr;(E) communication and &OHgr;(D) time. For the general (weighted) shortest paths problem, previously known shortest-paths algorithms required O(k · V2) messages and O(V · logk V) time. Our algorithm requires O(E1 + &egr; · log W) messages and O (V1 + &egr; · log W) time. Our results enable to improve significantly solutions for other basic network problems (e.g. leader election).

REFERENCES

• AG85: Baruch Awerbuch and Robert G. Gallager. Distributed bfs algoritlhms. In 26th Annual Symposium on Foundai!ions of Computer Science, IEEE, October 1985.
• AG87: 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]
• AGLP88: Baruch Awerbuch, Andrew Goldberg, Michael Luby, ~nd Serge Plotkin. Fast deterministic distributed maximal independent set algorithm. December 1988. Unpublished manuscript.
• Awe85: 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]
• Awe87: 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]
• DS80: Edsger W. Dijkstra and G. S. Scholten. Termination detection for diffusing computations. Info. Proc. Lett., 11(1):1-4, August 1980.
• Fre85: G N Frederickson, A single source shortest path algorithm for a planar distributed network, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.143-150, December 1985, Saarbru:9Aicken, Germany
• Gab85: Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
• Gal82: Robert G. Gallager. Distributed Minimum Hop Algorithms. Technical Report LIDS-P-1175, MIT Lab. for Information and Decision Systems, January 1982.
• Jaf80: Jeffrey Jaffe. Using signalling messages instead of clocks. 1980. Unpublished manuscript.
• Lub86: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• Lub88: Michael Luby. Removing randomness in parallel computation without a processor penalty. In 29th Annual Symposium on Foundations of Computer Science, Comp. Soc. of the IEEE, IEEE, 1988.
• MRR80: John M. McQuillan, Ira Richer, and Eric C. Rosen. The new routing algorithm for the ARPANET. IEEE Trans. Comm., 28(5):711- 719, May 1980.
• Pel87: David Pcleg. Fast leader elections algorithms. 1987. unpublished manuscript.
• PU88: David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62217]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Network communications

General Terms:
Algorithms, Design, Theory