Dynamic distributed programming and applications to all best swap edges problem.

摘要

Link failure is a common reason for disruption in communication networks. If communication between processes of a weighted distributed network is maintained by a spanning tree T, and if one edge e of T fails, communication can be restored by finding a new spanning tree, T'. If the network is 2-edge connected, T' can always be constructed by replacing e by a single edge, e', of the network. We refer to e' as a swap edge of e.;The best swap edge problem is to find the best choice of e', that is, that e which causes the new spanning tree T' to have the least cost, where cost is measured in a way that is determined by the application. Two examples of such measures are total weight of T' and diameter of T'.;The all best swap edges problem is the problem of determining, in advance of any failure, the best swap edge for every edge in T. The justification for this problem is that we wish to be ready, when a failure occurs, to quickly activate a replacement for the failed edge.;In this thesis, we give algorithms for the all best swap edges problem for six different cost measures. We first present an algorithm which can be adapted to all six measures, and which takes O ( d2) time, where d is the diameter of T. This algorithm is essentially a form of distributed dynamic programming, since we compute the answers to sub problems at each node of T.;We then present a novel paradigm for speeding up distributed computations under certain conditions. We apply this paradigm to find O(d)-time distributed algorithms for the all best swap edge problem for all but one of our cost measures.;Formal algorithms and their correctness proofs will be given.