Distributed and Fault-Tolerant Construction of Low Stretch Spanning Tree

Gurjar, Aishwarya and Peri, Sathya and Sengupta, Sinchan (2020) Distributed and Fault-Tolerant 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 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.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Gurjar, Aishwarya	UNSPECIFIED
Peri, Sathya	UNSPECIFIED
Sengupta, Sinchan	UNSPECIFIED

Item Type:

Conference or Workshop Item (Paper)

Uncontrolled Keywords:

Communication overheads; Connected component; Deterministic distributed algorithms; Error-prone environments; Low stretch spanning trees; Minimum spanning trees; Spanning tree construction; Underlying graphs

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

06 Aug 2021 06:23

Last Modified:

06 Aug 2021 06:23

URI:

http://raiithold.iith.ac.in/id/eprint/8707