Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree

Introduction: 

This paper discussed about a distributed algorithm to compute all best swap edges for a minimum diameter spanning tree.   A Minimum Diameter Spanning Tree minimizes the largest distance between any pair of nodes, even if edge lengths are not uniform. 

Overview: 

One drawback of a spanning tree is that a single link failure disconnects the network. Whenever link failures occur, it has to replace by a single other link called swap link to reconnect the network. Among all possible swap links, there is a need to choose a best swap to minimize the resulting swap tree diameter.

Swap tree does not use the failed link like a minimum diameter spanning tree. The reason for preferring a swap tree is only one edge goes into service and routing can be managed with less effort. There is a moderate loss in diameter in choosing swap tree against adjusting an entire tree. When compared to that of the diameter of an entire adjusted tree which is a factor of 2.5 smaller than the swap tree diameter. There is a need to pre-compute each edge of the tree to get a best swap edge. Distributed computation of all best swaps has more efficiency as dependencies between the computations for failing edges can be exploited.  When a failing edge is replaced by a best swap edge, we have a compact routing scheme for trees which can quickly and inexpensively adapt routing in distributed algorithm.  

Distributed algorithm computes the best swap edge for every failing edge depends on the information available after the pre processing phase. To compute all best swap edges of a tree there is a need to execute this algorithm for each edge of tree independently. 

Conclusions: 

When computing best swap edges for a minimum diameter spanning tree, the solution obtained by this paper is asynchronous, needs a unique identifiers from a linearly ordered universe also uses time, small messages or messages size.