A Distributed Algorithm for Disjoint Paths in Star Networks

A. Hamad and M.H. Karaata (Kuwait)


Cayley graphs, communication networks, hypercubes, load balancing, node-disjoint paths, routing algorithms, star networks.


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 thereafter. Whereas, a stabilizing system that maintains no explicit variables in the processes of the system is referred to as an inherently stabilizing system, and hence all system states are legal by construction. Due to this attribute, inherently stabilizing systems are immune to transient faults 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, star networks and their variations that provide an 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.

Important Links:

Go Back