Randomized distributed shortest paths algorithms

Published 1 January 1989Open access

Baruch Awerbuch

Citations30

TL;DR

A distributed algorithm for finding shortest paths in an asynchronous communication network and its results enable to improve significantly solutions for other basic network problems (e.g. leader election).

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 Θ(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.

Keywords

Computer Science

SIAM Journal on ComputingA Simple Parallel Algorithm for the Maximal Independent Set Problem

1,134 Citations1986Michael Luby

Journal of the ACMComplexity of network synchronization

691 Citations1985Baruch Awerbuch

A new simulation technique, referred to as a synchronizer, which is a new, simple methodology for designing efficient distributed algorithms in asynchronous networks, is proposed and is proved to be within a constant factor of the lower bound.

View PDF

Information Processing LettersTermination detection for diffusing computations

683 Citations1980Edsger W. Dijkstra, Carel S. Schölten

IRE Transactions on Communications SystemsThe New Routing Algorithm for the ARPANET

680 Citations1980John M. McQuillan, I. Richer +1 more

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations.

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

328 Citations1987Baruch Awerbuch

New linear time distributed algorithms for a class of problems in an asynchronous communication network, including Minimum-Weight Spanning Tree, Leader Election, and computing a sensitive decomposable function are developed.

Journal of Computer and System SciencesScaling algorithms for network problems

200 Citations1985Harold N. Garbow

Journal of Computer and System SciencesRemoving randomness in parallel computation without a processor penalty

194 Citations1993Michael Luby

IEEE Transactions on Information TheoryA new distributed algorithm to find breadth first search trees

131 Citations1987Baruch Awerbuch, Robert G. Gallager

A new distributed algorithm is presented for constructing breadth first search (BFS) trees, a tree of shortest paths from a given root node to all other nodes of a network under the assumption of unit edge weights.

A tradeoff between space and efficiency for routing tables

117 Citations1988David Peleg, Eli Upfal

It is proved that any routing scheme for general n-vertex networks that achieves a stretch factor k must use a total of &OHgr;(n1+1/2 +4) bits of routing information in the networks, and presents almost tight upper and lower bounds for this tradeoff.

View PDF

Distributed Minimum Hop Algorithms

66 Citations1982Robert G. Gallager

The control of data communication networks (and any other large distributed systems) must be at least partly distributed because of the need to make observations and exert control at the various nodes of the network.

View PDF