Paper Info
Title
A Stabilizing Algorithm For Finding Two Node-Disjoint Paths In Arbitrary Networks
Abstract
The problem of two node-disjoint paths is to identify two paths Q(1) and Q(2) from source s is an element of V to target t is an element of V without any common intermediate node in a communication network G = (V, E), where each node (vertex) in V denotes a process and each edge (p, q). E denotes a communication channel between nodes p and q. In this paper, we present the first adaptive stabilizing algorithm for finding a pair of node-disjoint paths in a semi-anonymous arbitrary network in O(D) rounds and the state-space complexity is O(log D) bits per process, where D is the diameter of the communication network. The algorithm assumes weakly fair distributed daemon and the knowledge of an upper bound on the number of processes by each process. If two disjoint paths exist between s and t, two disjoint paths are guaranteed to be constructed. In addition, the algorithm detects if two node-disjoint paths exist or not. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. The proposed algorithm has a wide range of applications in ensuring reliability and security of sensor, mobile and fixed communication networks.
Year
DOI
Venue
2017
10.1142/S0129054117500253
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
All node-disjoint paths, two node-disjoint paths, distributed systems, fault-tolerance, stabilization.
Discrete mathematics,Disjoint sets,Telecommunications network,Vertex (geometry),Upper and lower bounds,Communication channel,Algorithm,Fault tolerance,Floyd–Warshall algorithm,Initialization,Mathematics
Journal
Volume
Issue
ISSN
28
4
0129-0541
Citations 
PageRank 
References 
0
0.34
19
Authors
3
Name
Order
Citations
PageRank
Rachid Hadid1314.93
Mehmet Hakan Karaata219419.62
Vincent Villain354445.77