Randomized distributed shortest paths algorithms
Baruch Awerbuch · 1989
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 Θ(V) time, or Θ (E + V · D) communication. We present new algorithm, which requires O(D1+ε) time, and O(E1+ε) messages, for any ε > 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 Ω(E) communication and Ω(D) time.