A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks

The purpose of the paper is to present the first self-stabilizing algorithm for finding [Formula: see text] one-to-many node-disjoint paths in message passing model. Two paths in a network are said to be node disjoint if they do not share any nodes except for the endpoints. Our proposed algorithm works on n-dimensional star networks [Formula: see text]. Given a source node s and a set of [Formula: see text] of [Formula: see text] destination nodes in the n-dimensional star network, our algorithm constructs [Formula: see text] node-disjoints paths [Formula: see text], where [Formula: see text] is a path from s to [Formula: see text], [Formula: see text]. Since the proposed solution is self-stabilizing [7], it does not require initialization and withstands transient faults. The stabilization time of our algorithm is [Formula: see text] rounds.