Title:	A STABILIZING ALGORITHM FOR FINDING ALL NODE-DISJOINT PATHS IN STAR NETWORKS
Author(s):	Ahmad M. Hammad , Mehmet Hakan Karaata
ISBN:	978-972-8924-56-0
Editors:	Nuno Guimarães and Pedro Isaías
Year:	2008
Edition:	Single
Keywords:	Cayley graphs, communication networks, hypercubes, load balancing, node-disjoint paths, routing algorithms, star networks.
Type:	Short Paper
First Page:	410
Last Page:	414
Language:	English
Cover:
Full Contents:	click to dowload
Paper Abstract:	A stabilizing system guarantees that, regardless of the current configuration, the system reaches a legal configuration in a bounded number of steps and the system configuration remains legal there after. Whereas, a stabilizing system that maintains no explicit variables in the process of the system is referred to as an inherently stabilizing system, and hence all system state are legal by construction. Due to this attribute, inherently stabilizing systems are immune to transient fault and do not experience any delay due arbitrary system initialization. We view a fault that perturbs the system configuration but not the program as transient fault. Due to these features, inherently stabilizing distributed protocols for peer-to-peer, sensor and mobile networks are desirable. Hypercube, and star networks and their variations that provide increased degree of scalability have been initially design for parallel networks. However, their scalability and the presence of multiple disjoint paths in these topologies make them viable alternatives to existing peer-to-peer and sensor networks topologies. In this paper, we proposed an inherently stabilizing algorithm for delivering messages over all node-disjoint paths from a process to another in star networks, the proposed algorithm has numerous applications including VLSI layout, reliable networks routing, secure message transmission, and network survivability. The proposed routing algorithm is optimal with respect to its state space and lengths of the node-disjoint paths.
	Go Back