Gurjar, Aishwarya and Peri, Sathya and Sengupta, Sinchan
(2020)
Distributed and FaultTolerant Construction of Low Stretch Spanning Tree.
In: Proceedings  2020 19th International Symposium on Parallel and Distributed Computing, ISPDC 2020, 5 July 2020  8 July 2020.
Full text not available from this repository.
(
Request a copy)
Abstract
Spanning trees are widely used as a communication backbone over some given infrastructure and help network designers achieve a lowcost 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 spanningtree constructions resilient to edge failures in an errorprone 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 faulttolerant. The distributed ABSE computation in our case equals the stateoftheart running time of O(h) rounds, where h is the height of the tree.
[error in script]
Actions (login required)

View Item 