Distributed and Fault-Tolerant Construction of Low Stretch Spanning Tree

Spanning trees are widely used as a communication backbone over some given infrastructure and help network designers achieve a low-cost communication overhead. Spanning trees are generally designed, keeping in mind some optimizing metric (most general being sum of edge weights in a Minimum Spanning Tree) with respect to the underlying graph. For applications that require preserving shortest path distances between nodes of the weighted underlying graph in the abstracted spanning tree, we look to minimize a parameter known as stretch. Stretch is defined as the ratio of the distance between two nodes in the tree to its shortest path distance in the communication graph. To make spanning-tree constructions resilient to edge failures in an error-prone environment, we consider what is called the All Best Swap Edges (ABSE) problem. Since every edge in a tree is a bridge edge, a single edge failure disconnects the tree into two connected components. In the ABSE problem, for each edge e in the spanning tree, we compute a swap edge f corresponding to e, that is activated when e fails. f helps to restore the communication in the tree by connecting the disconnected components. In this paper, we give a novel distributed algorithm to efficiently construct a low average stretch spanning tree and make it robust against edge failures by finding a swap edge for every edge in the constructed tree. This is the first known deterministic distributed algorithm for constructing a low stretch tree that is also edge fault-tolerant. The distributed ABSE computation in our case equals the state-of-the-art running time of O( h) rounds, where h is the height of the tree.