Distributed algorithms for computing shortest pairs of disjointpaths |
| |
Authors: | Ogier R.G. Rutenburg V. Shacham N. |
| |
Affiliation: | SRI Int., Menlo Park, CA; |
| |
Abstract: | Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied |
| |
Keywords: | |
|
|