key: cord-0044934-3jxi0dj2
authors: Hadid, Rachid; Villain, Vincent
title: A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks
date: 2020-05-15
journal: Distributed Applications and Interoperable Systems
DOI: 10.1007/978-3-030-50323-9_12
sha: 630fddb688f7d37aed1fd1a8c941d22253f5353d
doc_id: 44934
cord_uid: 3jxi0dj2

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.

The concept of self-stabilization [7] is the most general technique to design a system to tolerate arbitrary transient (in other words, limited in time) faults. A self-stabilizing system, regardless of the initial states of the processors and initial messages in the links, is guaranteed to converge to the intended behaviour in finite time. We view a fault that perturbs the state of the system but not its program as a transient fault. The problem of finding disjoint paths in a network has been given much attention in the literature due to its theoretical as well as practical significance to many applications, such as layout design of integrated circuits [22] , communication protocols [10] , secure message transmission [24] , survivable design of telecommunication networks [23] and reliable routing [15] . Node disjoint paths can be used for secure communication by breaking up data into several shares and sending them along the disjoint paths to make it difficult for an adversary with bounded eavesdropping capability to intercept a transmission or tamper with it. Network survivability reflects the ability of a network to maintain service continuity during and after failures. In practice, it is important to construct node disjoint paths in networks, because they can be used to enhance the transmission reliability. Alternatively, the same crucial message can be sent over multiple node disjoint paths in a network that is prone to message losses to avoid omission failures, or information on the re-routing of traffic along non-faulty disjoint paths can be provided in the presence of faults in some disjoint paths. Routing is a process of transmitting messages among nodes, and its efficiency is crucial to the performance of a network. Efficient routing can be achieved by using internally node disjoint paths, because they can be used to avoid congestion, accelerate transmission rate, and provide alternative transmission routes. Moreover, node disjoint paths between two processes present additional benefits such as broadening the network bandwidth and load balancing of the network by allowing communicating pair of processes to distribute the communication load on node disjoint paths without congesting communication channels in the network. There are three paradigms for the study of node disjoint paths in interconnection networks: the one-to-one, and the one-to-many, and the many-to-many node disjoint paths [8] . The one-to-one node disjoint paths constructs the maximum number of node disjoint paths in the network between two given nodes, and the one-to-many node disjoint paths constructs node disjoint paths in the network from a given node to each of nodes in a given set. The one-to-many node disjoint paths problem are fundamental and extensively studied in graph theory. One-to-many node disjoint paths were first presented in [26] where the Information Dispersal Algorithm (IDA) was proposed on the hypercube. Some algorithms to find one-to-many node disjoint paths in a variety of networks are proposed in [5, 6, 8-10, 14, 17-19, 21, 25] . Let G = (V, E) be a connected graph, where V and E represent the node set and edge set of G, respectively. Throughout this paper, we use network and graph, processor and node, and link and edge, interchangeably. The n-dimensional star network (n-star for short) [1] [2] [3] is one of most efficient and popular interconnection networks because of its attractive properties, including regularity, node symmetric, small diameter, and recursive construction. The n-star network, denoted as S n = (V, E), is a bidirected graph consisting of n! nodes, each node is identified with a distinct permutation of n symbols 1, 2, . . . , n. There is a link between any two permutations (nodes) iff one can be reached from the other by interchanging its first symbol with any other symbol. More precisely, the node representing permutation a 1 a 2 . . . a i−1 a i a i+1 . . . a n have links to n-1 other permutations (nodes) a i a 2 . . . a i−1 a 1 a i+1 . . . a n , for some 2 ≤ i ≤ n. The node with the permutation 123 . . . n will be called the identity node. Figure 1 illustrates the 3-star and 4-star systems. The construction of the one-to-many node disjoint paths in the n-star has also been considered by researchers in graph theory [5, 8, 29] . The disjointness of these paths is ensured by using different approaches. In a first approach [29] , we can fix a particular symbol j, 1 ≤ j ≤ n, at the last position of all the nodes on the path noted P j . So, all the nodes of the path P j (except for at most one) have a common symbol j at the last position of their permutations. Hence, each selection of the symbol j, 1 ≤ j ≤ n, will make the path P j node disjoint from the others paths. The following example illustrates the concepts (see example 1).

Example 1. Assume that we have 4-star system and let s = 1234 and D = {4321, 1342, 4123, 2134}. We construct 4 node disjoint paths P 1 , P 2 , P 3 and P 4 from s to each destination process d 1 = 4321, d 2 = 1342, d 3 = 4123, and d 4 = 2134, respectively, by fixing the symbols 1, 2, 3, and 4 at the last position of all the nodes (except for at most one) on P 1 , P 2 , P 3 , and P 4 , respectively. The node disjoint paths P 1 , P 2 , P 3 , and P 4 may look as follows.

Where the underlined digit denotes the swapped one.

However, since n-star graphs are node symmetric, the position at which to fix the symbol j does not have to be the last one, as shown in [8] . The position at which we fix our symbols could be i for 2 ≤ i ≤ n. Therefore, we have n − 1 ways of fixing the symbol j in the path noted P j i , where i denotes the position where the symbol j is fixed. So, for each path P j i is designed a unique position i, 2 ≤ i ≤ n, and a distinct symbol j, 1 ≤ j ≤ n, such that i is the position of the symbol j in all the permutations (except for at most one) of the nodes on the path P j i . We can illustrate this approach by using the following example (see example 2).

Example 2. Assume that we have 4-star system and let s = 1234 and D = {4321, 1342, 4123}. We construct 3 node disjoint paths P 1 2 , P 2 3 , and P 3 4 by fixing the symbols 1, 2, and 3 at the second, third, and fourth position for each node on the path P 1 2 , P 2 3 , and P 3 4 , respectively. (i) A path P 1 2 from s to d 1 = 4321 that keeps the symbol 1 at position 2 may look as follows:

3 from s to d 2 = 1342 that keeps the symbol 2 at position 3 may look as follows:

4 from s to d 3 = 4123 that keeps the symbol 3 at position 4 may look as follows:

However, this solution can be simplified as follows [5] . We may choose to fix the same symbol j, 1 ≤ j ≤ n, over all the node disjoint paths, but in different positions i for 2 ≤ i ≤ n. So, for each path P i , the same symbol j is fixed at the same position i in all processes on the path P i , except for at most one. The following example illustrates the concepts (see example 3).

Example 3. Assume that we have 4-star system and let s = 1234 and D = {4321, 1342, 4123}. We construct 3 node disjoint paths P 2 , P 3 , and P 4 by fixing the symbol 1 (j = 1) at the second, third, and fourth position for each node on the path Self-stabilizing algorithms to find node disjoint paths are proposed in [11, 12, 16, 28] . Self-stabilizing algorithms for finding one-to-one node disjoint paths between two endpoints for hypercube and mesh networks have been proposed in [11, 28] , respectively. A new self-stabilizing algorithm for finding two one-to-one node disjoint paths problem in arbitrary network was proposed in [12] . The basis of the algorithm was outlined in [16] as a brief announcement. It has been shown that finding the node disjoint paths is NPhard in general graphs [13] . For n-dimensional hypercubes H n (which has diameter d(H n ) = n), it was proved that n disjoint paths for the one-to-one node disjoint paths paradigm [27] and n disjoint paths for the one-to-many node disjoint paths paradigm [26] can be found in O(n 2 ) time. For n-dimensional star graphs, (which has diameter d(S n ) = 3(n−1) 2 ), it was shown that n − 1 disjoint paths for one-to-one node disjoint paths paradigm can be found in O(n 2 ) time [20] and n − 1 disjoint paths for one-to-many node disjoint paths can be found in O(n 2 ) time [8] . The time complexity of the above self-stabilizing algorithms is as follows: O(d) rounds for algorithm [11] (working in mesh network), whereas the time complexity of the algorithms [12, 16, 28] is O(d 2 ) rounds, where d the diameter of the network.

In this paper, we present the first self-stabilizing distributed algorithm for finding n − 1 node-disjoint paths between the source process s and n − 1 other destination processes {d 1 , d 2 , ..., d n−1 } in the n-star network. While it takes the same polynomiale O(n 2 ) rounds to solve the same problem by the result in [5, 8, 29] . We propose a method based on message-passing techniques to process global information, which is more approach to reality. We adapt the approach used in [5] to ensure the disjointness of these n − 1 paths. Unlike previous solutions, our algorithm does not utilize the cycle presentation of the permutations, making it easy to understand. Our approach is different from the previous one [5] in that the disjoint paths are constructed from the source s to the n − 1 processes in the n-star. This makes our solution more suitable to implement. In addition, it reveals interesting functions to implement the disjointness of the paths in a self-stabilizing distributed environment.

The rest of the paper is organised as follows. In Sect. 2, we describe the distributed system model used in this paper. Then, we present the one to many node disjoint paths algorithm in Sect. 3 and its correctness proof in Sect. 4. Finally, we make some concluding remarks in Sect. 5.

Our algorithm is designed to operate on an asynchronous distributed system modelled as an n-star network. A transposition π[1, i] on a permutation p, noted π [1, i] (p), is to exchange the positions of the first and the ith symbol in the permutation p. For example, if p = a 1 a 2 ...a i−1 a i a i+1 ... a n , then π[1, i](p) = a i a 2 ...a i−1 a 1 a i+1 ...a n . There is a link between any two processes p and q if and only if π [1, i] (p) = q, for some 2 ≤ i ≤ n. We will use a process identity (process name) in a star network to refer also to the permutation that labels the process. We consider the message-passing model where communication between neighboring processes is carried out by messages exchanged through bidirectional links, i.e., each link can be seen as two channels in opposite directions. A distributed protocol for such a message passing system consists of a collection of n local programs, one for each processor in the system. This local program provides the ability to the processor either to perform local computations, or to send and receive messages from each of its neighbours in the n-star network. More precisely, the program consists of a collection of actions. Overall, an action is of the form: <guard>::<statements>. A <guard> is mainly triggered when an input message is received. In addition, tools like timer or randomly and spontaneous are used in the <guard>. <statements>, executed when a <guard> is activated, is a sequence of assignments/computations, invoking functions/procedures, and/or message sending. Note that an action can be executed only if its guard is activated. A message is of the following form: (type, value). A message may also contain more than one value. We define the state of each process to be the state of its local memory and the contents of its incoming channels. The global state of the system, referred to as a conf iguration, is defined as the product of the states of processes. We denote by C the set of all possible configuration. An execution of a protocol P in a system S is an infinite sequence of configurations γ 0 , γ 1 , ..., γ i ... such that in any transition γ i → γ i+1 either a process take a step. We assume that the message delivery time is finite but unbounded. We also consider a message in transit until it is processed by the receiving processor. Moreover, each link is assumed to be of bounded capacity, FIFO, and reliable (the messages are not lost and delivered UN-corrupted) during and after the stabilization phase.

In this section, we first present the basis description of the proposed solution. Given a process s and n − 1 other distinct processes D = {d 1 , d 2 , . . . , d n−1 } in the n-star system, the proposed algorithm constructs n − 1 node-disjoint paths P 1 , P 2 , . . . , P n−1 , where P h is the path from s to d h , for h = 1, 2, . . . , n−1. Note that the algorithm works also for D = {d 1 , d 2 , . . . , d m } such that m < n. Our solution works in two phases referred to as labeling phase (Algorithm 2) and One-T o-Many node-disjoint paths construction phase (Algorithm 4). The One-T o-Many node-disjoint paths construction phase is based on the labeling process phase, i.e., the progress of this phase is ensured only after the labeling process terminates successfully. During the labeling phase, each destination process d h , 1 ≤ h ≤ n − 1, in D should be labeled by a unique label j, 2 ≤ j ≤ n, such that the index j is the reserved position for the symbol 1 for the processes on P j connecting process s to process d h . So, after this phase the set D =

During the One-T o-Many node-disjoint paths construction phase, we construct n − 1 node-disjoint paths P 2 , P 3 , . . . , P n from the source process s to the new labeled destination processes (d 1 , j 1 ), (d 2 , j 2 ), . . . , (d n−1 , j n−1 ) such that each path P j , 2 ≤ j ≤ n, connects the source process s to a destination process (d h , j) ∈ DL. For each path P j , 2 ≤ j ≤ n, we reserve a unique position j for the path, such that, for all processes on P j (except for maximum two processes) the symbol 1 is at jth position in the permutations. In other words, we construct each path P j , 2 ≤ j ≤ n, from the source process s to the destination process (d h , j) ∈ DL and keeps the symbol 1 in a fixed position j along all the processes on P j , except for maximum two processes.

Prior to the presentation of these two phases in details, we first present Algorithm 1 which computes the shortest distance between the source s and a destination d (Function Dist(s, d) ). This metric is needed during the labeling phase. A shortest path P from a process s in the n-star system S n to a destination process d is given by the following two rules [3] . Assuming that the shortest path P is built up to the process p = d (initially, p = s), then the successor of p on P is identified as follows (See Function NextNeigh() in Algorithm 1). Let x be the first symbol in the permutation of p, then (r 1 ) If there exists a symbol y in the kth position,

denotes the symbol at the position k on a permutation d). In other words, x directly reaches its correct position in d.

(r 2 ) Otherwise, exchange x with the symbol y in the kth position such that y is not in a correct position in d, y = d[k], if exists (i.e., ByP ass p = ∅). If multiple such symbols exist, then choose the symbol y with the smallest position in the permutation d. In other words, y, which is in incorrect position, is temporarily placed in the first position. Thereafter, it is moved to its correct position by applying rule (r 1 ). The Function Dist(s, d) computes in dist (using Function NextNeigh()) the number of steps needed to built a shortest path from the source s to the destination d. The following example illustrates the distance computing between s and d in 5-star system (see example 4).

The distance computing, using the path P created by the rules (r 1 ) and (r 2 ), from s to d = 51243 looks as follows:

The distance computing between s and d = 14523 looks as follows. = 6] . Where the value in brackets indicate the value of dist at a process, and the rule used to swap to the next process is indicated between parentheses on the arrow.

It is shown in [3] that this algorithm will always find the shortest path from s to d in S n . It has been also shown in [3] that the diameter of S n is equal to 3(n − 1)/2 .

The labeling phase is handled by the source process s (Algorithm 2 and Function Labeling()). Let D = {d 1 , d 2 ...., d n−1 } be a set of n − 1 distinct processes in the n-star network S n . During this phase, each destination process d h , 1 ≤ h ≤ n − 1, in the set D is labeled by a unique label j, 2 ≤ j ≤ n. Thereafter, we denote by DL the set of the new labeled processes (d h , j), 2 ≤ j ≤ n. The index j, 2 ≤ j ≤ n, associated to each destination d h , refers to the unique fixed position of the symbol 1 along all the processes on the path P j (except for maximum two processes) connecting s and d h . Process p in the n-star network S n is a (1)-process if 1 is the first symbol in the permutation p. Process p in S n is a (i 1)-process, where 2 ≤ i ≤ n, if 1 is the ith symbol in the permutation p. The set DL is implemented using an array of structure where each element of the array in the position pos, 1 ≤ pos ≤ n − 1, contains the couple (id, lab) where id and lab represent the permutation (d h ) and the label (j) associated to the processs d h , respectively. The labeling process is implemented by repeating the following three simple rules (L 1 ), (L 2 ), and (L 3 ). Note that the index pos is initiated to 1 and is increased each time a new element is added to DL. (L 2 ) Then, for each process d h in the set D such that d h is a (i 1)-process, but not a representative process for a subset D i , reserve a position j for d h with 2 ≤ j ≤ n, that is not already assigned to any process in D, then d h is labeled by j. Similarly to (L 1 ), the process d h is deleted from D and (d h , j) is inserted into DL.

(L 3 ) Finally, for each d h in the set D such that d h is a (1)-process reserve a position j for d h with 2 ≤ j ≤ n, that is not already assigned to any process in D, then d h is labeled by j. Similarly to (L 1 ), the process d h is deleted from D and (d h , j) inserted into DL. Note that all (i 1)-processes are labeled before (1)-processes. In order to illustrate the above concepts, we provide the following example (see example 5) From the above, it is clear that all representative processes appear before all other processes in the array DL. In addition, the (i 1)-processes appear after the representative processes and before other remainder processes, i.e., (1)-processes. In the sequel, we assume that all the processes in DL are identified based on their positions in the array DL. Thus, the process in the position one is denoted by d 1 and the process in the second position is denoted by d 2 and so on. For the sake of simplicity, each element (d h , j) in DL is denoted by d h .j, where d h refers to the process at the position h, 1 ≤ h ≤ n − 1, and j, 2 ≤ j ≤ n, is the label assigned to d h . Moreover, we use the notation d.j, when the rank h of the process d in DL is omitted, to refer simply to a process d in DL indexed by a label j.

Upon completion of the labeling phase, each process d.j in DL is assigned a unique label j, 2 ≤ j ≤ n, such that j is the position of the symbol 1 in all the permutations (except for at most two) of the processes on the path P j connecting s to d.j. During this second phase, n − 1 node-disjoint paths, noted by P 2 , P 3 , . . . , P n , are constructed from the source s to the destination processes in DL such that each path P j , 2 ≤ j ≤ n, connects the source process s to the destination process d.j. In order to carry out this task, we need to solve the following two problems: (i) We need a procedure that constructs a path from the process s to a destination process d.j, 2 ≤ j ≤ n, and keeps the symbol 1 in a fixed position j along all the processes on the path P j , except for at most one process. (ii) All these paths P 2 , P 3 , ..., P n must be node-disjoint.

The basic construction (property (i)) is referred to as elementary construction and is implemented basically using Function NextNeighFix1() (see Algorithm 3, namely the One-T o-One Fix-1 path construction algorithm) and the message (d, j) containing two parameters, the destination d and the position j of the symbol 1 in all the processes on the path P j (see Actions a 21 and a 3 , Algorithm 4). Observe that, under certain circumstances (i.e., a non-elementary construction), where the destination d is said to be marked (Function Marked()), Algorithm One-T o-Many disjoint paths uses another message containing three parameters (see Actions a 22 and a 4 , Algorithm 4). Now, we describe the elementary construction and the purpose of the second one (nonelementary construction) is discussed later. The processes in this construction exchange one type of message containing two parameters: destination d and the fixed position j, 2 ≤ j ≤ n, of the symbol 1 along the processes on P j . Once the elementary construction is started, the source process s initiates the construction of the path P j from s to d.j by sending the message (d, j) to its successor on P j (Action a 21 ). Subsequently, each process p (p = d), upon receipt of this message, transmits the message to its successor process on the path P j (Action a 3 ). Each process uses the function NextNeighFix1() to identify the successor process on the path P j that kept the symbol 1 in the same fixed position j. The function NextNeighF ix1(d, j) contains also two parameters, the destination d and the position j of the symbol 1 in its successor process on the path P j . This function is implemented by executing one of the following six rules: (r 0 ), (r 1 ),. . . , and (r 5 ) (see Algorithm 3 and Function NextNeighF ix1()). The rules are executed in the order they are written. So, if the first rule is not applicable, then we try the next rule and so on. Assuming that the shortest path from s to d is built up to the process p = d (initially, p = s), then the successor of p is identified as follows. Let x be the first symbol in the permutation of p, then (r 0 ) This rule is executed one time and only by the source process s, during the initialization phase. So, p is the identity process s (Predicate Source(p)), exchange the first symbol 1 with the jth symbol in s. In this rule, the symbol 1 is moved to the desired position j in the destination d. ByP ass1(p) ). In this rule, we move x to a position k not occupied by a correct symbol, i.e., p[k](= y) = d [k] . If multiple positions are not occupied by a correct symbol, then choose the symbol with the smallest position. Similarly to the case (r 1 ), to maintain the symbol 1 in a fixed position, y should not be equal to 1. In addition, to maintain the path P j as shortest as possible, y should be different than d [1] and d [j] . A (1)-process associated with the process d.j, 2 ≤ j ≤ n, such that d.j is an (i 1)process, is the process obtained from d.j by swapping its first symbol with the symbol 1 located at position i (i.e., π [1, i] (d.j) ). Remark 1. From the above elementary construction we deduce the following remarks. (i) If d.j is a representative process of a set D j , then all the processes of the path P j constructed from s to d.j are (j 1)-processes, except s (see example 6 case (a)). (ii) If d.j is a (1)-process, then all the processes of the path P j are (j 1)-processes, except the endpoints s and d.j (see example 6 case (b)). (iii) If d.j is a (i 1)-process (i = j), then all the processes of the path P j are (j 1)processes, except the (1)-process associated with the process d.j and its endpoints s and d.j (see example 6 case (c)). Now, we are ready to present the remainder of the One-T o-Many node-disjoint paths algorithm (i.e., the non-elementary construction). Observe that from Remark 1, if all the processes in DL are representative processes (j 1)-processes and/or (1)-processes, then the One-T o-Many node-disjoint paths algorithm is obviously obtained by applying the elementary construction from the source s to each destination process d.j, 2 ≤ j ≤ n in DL. Since for each destination process d.j, 2 ≤ j ≤ n, there exists a distinct position j which is reserved for the symbol 1 for all the processes on the path P j . So, each path P j , 2 ≤ j ≤ n, connecting s to d.j is node disjoint from the other paths. This is illustrated in the following example (see example 7). A (1)-process associated with the (i 1)-process d h ∈ DL, 2 < h ≤ n, (that is not a representative process) is said marked process (Function Marked(), Algorithm 4) if it is equal to the (1)-process associated with another (i 1)-process d h such that 1 ≤ h < h, i.e., the path to the destination d h is constructed before the path to the destination d h . A critical step in applying only the elementary construction to construct the n−1 One-T o-Many node-disjoint paths is the case 5 (rule (r 5 )) where for a given (i 1)-process d h ∈ DL, 2 < h ≤ n, that is not a representative process of the set D i , the (1)-process associated with d h is marked. So, in this case, there already exists a destination process d h ∈ DL, 1 ≤ h < h, such that its (1)-process is identical to the (1)-process associated with d h . In this situation, the (1)-process associated with d h already belongs to a previously constructed path, say P j , initiated by s to process d h before s initiates the construction of the path, say P j , to d h . Therefore, the two paths P j and P j are not node-disjoint, since they intersect at the (1)-process associated with the two processes d h and d h . We can illustrate this situation by using again the example 3 presented in Sect. 3.1 (example 8). Observe that, in the above example, the (1)-process 13452 associated with d 4 is marked, since it is equal to the (1)-process associated with d 2 . So, the paths P 2 and P 4 are not node-disjoint paths. To alleviate such a problem, the following scheme is introduced in the One-T o-Many disjoint algorithm. During the construction of nodedisjoint paths P 2 , . . . , P n (such that each path P j , 2 ≤ j ≤ n, connects the source s to the destination process d h .j, 1 ≤ h ≤ n − 1), each time a marked process associated with a (i 1)-process d h .j is identified (Function Marked(d, h) ), the path P j from s to d h is constructed as follows (i.e., the non-elementary construction). First, we need to identify a neighbour d .j of the process d h such that the process d .j is not in DL and the (1)-process associated with d .j is not marked. Note that each marked process is a (1)-process contained in a previously constructed paths. Then, the node-disjoint path P j from s to d h .j is constructed in the following two steps. First, the path P j is constructed from s to d .j. Then, the construction continues from d .j to d h .j. This is implemented by the introduction of the message (d , d, j) containing three parameters d , d, and j. Hence, the (1)-process associated with d h .j is not included in the path P j , whereas it includes the not marked (1)-process associated with d .j. We can illustrate this approach by using again the example 8 (see example 9). Example 9. From example 8, the paths P 2 and P 4 are not node-disjoint paths, since the 1-process associated with d. 2 The One-T o-Many node disjoint paths algorithm works as follows. After the labeling phase (Action a 1 ), each process in DL is assigned a unique label j, 2 ≤ j ≤ n. The source process s initiates the construction of the n − 1 node-disjoint paths P 2 , P 3 , . . . , P n such that each path P j , 2 ≤ j ≤ n, connects the source process s to the destination d h .j ∈ DL, 1 ≤ h ≤ n − 1 (Action a 2 ). Then, we need to consider two cases. (a) In the simplest case, when the destination process d h .j is in one of the three following situations (i.e., the (1)-process associated to d h is not marked): either it is a representative process of a set D i or, a (1)-process, an (i 1)-process and its associated (1)-process is not marked. In this case, the construction is elementary and is handled by the message (d h , j) containing two parameters, d h and j. So, once the source process s initiates this construction, it transmits the (d h , j) message to its successor on the path P j using function NextNeighFix1(). Analogously, when a process p (p = d h ) receives this message, it transmits the message to its successor on the path P j . This is repeated until the destination d h is reached. This is implemented using Actions (a 21 ) and (a 3 ). (b) However, when d h .j is an (i 1)-process and the (1)-process associated with the process d h .j is marked, then, as explained before (non elementary construction), we first identify a neighbour d .j of the process d h .j such that d .j is not in DL and the (1)-process associated with d .j is not marked. This is implemented using Function UMNeigh(). In this case, the construction is handled by using the message (d , d h , j) containing three parameters: the first and the second destinations d .j and d h .j to reach, respectively, and the position j of the symbol 1 along all the processes on the path P j . So, the source process s initiates the construction of the path P j from s to d by sending the message (d , d, j) to its successor on P j (Action (a 22 ) . Then, subsequently, upon a process p receives this message, we need to consider two cases (Action a 4 ). (i) If the process p is the first destination d , meaning that the first destination d is reached, then p sends the message (d h , j) with the second destination d h to reach to its successor; (ii) Otherwise, the first destination d is still not reached, then p transmits the message to its successor. Each process, upon receipt of a message, uses the function NextNeigh-Fix1() to identify the successor process on a path P j that kept the symbol 1 in the same position j.

We will show that Algorithm 4 constructs n − 1 one-to-many node-disjoint paths. From Algorithm 4, each destination process d.j in DL such that d.j is a representative process of a set D j , (1)-process, or a (i 1)-process and its associated 1-process is not marked (Function ¬Marked()), the elementary construction is sufficient to construct a path P j from s to d.j (Actions a 21 and a 3 ) . However, if d.j is a (i 1)-process and its associated (1)-process is marked, then we need to identify a neighbour process of d.j (say d .j) such that d .j is not in DL and its associated (1)-process is not marked (Function UMNeigh()). Then, the path P j is constructed in two steps: first a path is constructed from s to d .j, then from d .j to d.j (Action a 22 and a 4 ) . From Algorithm 4, we can claim the following lemma. Lemma 1. Let d.j ∈ DL a destination process, then Algorithm 4 constructs a path P j from s to d.j with the following properties. (i) If d.j is a representative process, then all the processes on P j keeps the symbol 1 at position j, except s. (ii) If d.j is a (1)-process, then all the processes on P j keeps the symbol 1 at position j, except its endpoints s and d.j.

, then all the processes on P j keeps the symbol 1 at position j, except the (1)-process associated with d.j, and at most two (i 1)-processes (i.e, d.j and one of its neighbour d .j in N j ), and s.

In the sequel, we need the following definition. We say that a process sequence (u 1 , u 2 , ..., u s ) in the n-star S n is a simple cycle if all processes are distinct and (u s , u 1 ), (u i , u i+1 ), 1 ≤ i ≤ s − 1, are all edges in S n . From [4] , we can claim the following result.

There is no simple cycle of the length less than six in the n-star S n .

Let PrevP j denote the set of all the paths built before the path P j . We introduce the definition of the sets N j and (1)-N j associated with each destination process d.j ∈ DL to facilitate the proof. Observe that each process d.j has n − 1 neighbours, one is a (1)-process and the others are (i 1)-processes. Let the n − 1 neighbours of d.j be

is the (1)-process associated with d.j and π[1, k](d.j), 2 ≤ k ≤ n and k = i, are the (i 1)-processes neighbours of d.j. Let N j = {d k , 2 ≤ k ≤ n and k = i} be the set of all the (i 1)-processes neighbours of d.j. Let (1)-N j = {(1)d k , 2 ≤ k ≤ n} be the set of all (1)-processes associated with processes in {d.j} ∪ N j such that (1)-d k is the (1)-process associated with d k .

Lemma 3. Let d.j ∈ DL be a (i 1)-process, but not the representative process, of set D i and let the sets N j and (1)-N j be defined as above. Then, each path P t of the paths PrevP j contains, at most, one process in N j and, at most, one process in (1)-N j .

Proof. Let P t ∈ PrevP j be the path that connects the source process s to the destination process d.t such that t is the position reserved for the symbol 1 for all the processes on P t (except for maximum one).

(t 1)-processes, t = j. The path P t contains at most one process in the set N j (i.e., the process d.t or d k ) and contains, at most, one process in (1)-N j (i.e., the (1)-process associated with d k ). If the (1)-process (1)-d k is in the set (1)-N j , then the process d.t cannot be in the set N j -otherwise, the process d k is not in the set N j and the process sequence (d t , d k , (1)-d k , d .j, d.j) would form a simple cycle of length 5 in the n-star (d .j is is a neighbour d.j on P j ). Lemma 5. Let d.j be a (i 1)-process, but not the representative process, of set D i . If the (1)-process associated with the process d.j is marked, then there is a neighbour d k of d.j such that the process d k and the (1)-process associated with d k are not marked.

Proof. By Lemmas 3 and 4, each previously constructed path P t ∈ PrevP j contains, at most, one process in N j (say, d k ), and, at most, one (1)-process in (1)-N j , the (1)process associated with d k . Let |PrevP j |= x ≤ n − 2. So, there exists x marked processes N j and x (1)-processes marked processes in the set (1)-N j . Thus, there exists (n − x − 1) ≥ 1 unmarked processes in the set N j along with their (n − x − 1) unmarked in the set (1)-N j , hence the result.

By Algorithms 2, 4 and Lemmas 1, 5, we can show this result by induction on the number of the node-disjoint paths previously constructed, i.e., |PrevP j |, such that 0 ≤ |PrevP j | ≤ n − 2.

Lemma 6. Let P j (2 ≤ j ≤ n) be the path constructed from s to d.j by Algorithms 4, then the path P j is node-disjoint with all paths PrevP j previously constructed by the algorithm. Theorem 1. Given a source s and a set D={d 1 , d 2 , ..., d n−1 } of n − 1 distinct processes in the n-star, Algorithm 4 is a self-stabilizing one-to-many node-disjoint paths algorithm and construct n−1 one-to-many node-disjoint paths in at most O(n 2 ) rounds, such that each path connects s to a process in D.

Proof. From Algorithm 4 and Action (a 1 ), the source process s initiates the labeling process infinitely often. The labeling process of the set D = {d 1 , d 2 , ..., d n−1 } uses the distance computing algorithm (Algorithm 2). In the worst situation, we have D 2 , D 3 , ..., D n/2 ⊆ D subsets such that each subset D i (i ∈ 2, 3, ..., n/2 ) contains two (i 1)-processes. So, in order to find the representative process of each subset D i (see rule (L 1 ), Algorithm 2), we need to compute the distance from s to each process in D i , i.e., 2( n/2 − 1) processes. Since, each distance computing needs at most 3(n−1)/2 rounds, where 3(n−1)/2 is the diameter of the S n , so the labling phases requieres 2( n/2 − 1)( 3(n − 1)/2 ) rounds (O(n 2 ) rounds). Then, from action (a 2 ), the source s also initiates the construction of the n − 1 node disjoint paths infinitely often. Then, from actions a 3 and a 4 each process participates in the construction of the paths infinitely often. From Lemma 4, the n − 1 node-disjoint paths are constructed in at most 3(n − 1)/2 rounds. Thus, the stabilization time is O(n 2 ) rounds.

In this paper, we presented the first distributed self-stabilizing algorithm for finding one-to-many node-disjoint paths algorithm 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 algorithm works on n-star networks S n . Due to being self-stabilizing, it tolerates transient faults, and does not require initial configuration. The stabilization time of our algorithm is O(n 2 ) rounds. In this work, we merely provided an algorithm to find one-to-many disjoint paths in n-star networks. Devising distributed and selfstabilizing algorithms for hypecube is open problem that we consider as future work.

all internal processes of P t are (t 1)-processes and t = j. Similarly, by Lemmas 1 case (iii), the path P j contains only (j 1)-processes, one (1)-process, and at most two (i 1)-processes and t = i, since the position i is reserved for the representative process of the set D i . Thus, the path P t contains no process in the set N j and contains at most one process, i.e., the process d.t, in (1)-N j . 2. If d.t is a (k 1)-process for k = t and k = i, then by Lemmas 1 case (iii), the path P t contains only (t 1)-processes, one (1)-process, and at most two (k 1)-processes and t = i. Since k = j (because there exists a representative process for each subset D k and D j )

Then, by Lemma 1 case (i), all processes except the first process s on the path P t are (i 1)-processes. Thus, the path P t contains no process in the set (1)-N j . To prove that the path P t contains, at most, one process in N j , assume the contrary, that P t contains two (i 1)-processes in the set N j (i

of the set D i . We need to consider two cases. a. The path P t contains only one (i 1)-process that is the process d.t and one (1)-process that is the (1)-process associated with d.t, and the rest of the processes on

one (1)-process that is the (1)-process associated with d k (i.e., (1)-d k ), and the rest of the processes on P t are all (t 1)-processes, t = j. In this case, not both of d.t and d k can be in the set N j ; otherwise, the star system S n would have a simple cycle

)-process, but not the representative process, of set D i and let the sets N j and (1)-N j be defined as above. Then, for each path P t of the paths PrevP j , if the path P t contains a process d k in the set N j and a (1)-process (1)-d l in the set (1)-N j

N j only in the case 4.b. The process d.t is a (i 1)-process, but not the representative process, of the set D i . The path P t contains two adjacent (i 1)-processes that is the process d

Group graphs as interconnection networks

A group theoretic model for symmetric interconnection networks

The star graph: an attractive alternative to the ncube

Combinatorial and algebraic methods in star and bruijn networks

Nearly optimal one-to-many parallel routing in star networks

On disjoint shortest paths routing on the hypercube

Self-stabilizing in spite of distributed control

Three disjoint path paradigms in star networks

Short containers in Cayley graphs

Node-to-set and set-to-set cluster fault tolerant routing in hypercubes

An adaptive stabilizing algorithm for finding all disjoint paths in anonymous mesh networks

A stabilizing algorithm for finding two node-disjoint paths in arbitrary networks

A graph theoretical study of transmission delay and fault tolerance

On container width and length in graphs, groups, and networks

A genetic algorithm for maximum edge-disjoint paths problem and its extension to routing and wavelength assignment problem

Briefannouncement: a stabilizing algorithm for finding two disjoint paths in arbitrary networks

One-to-Many disjoint paths in the hypercube and folded hypercube

Two conditions for reducing the maximal length of node-disjoint paths in hypercubes

Optimal construction of all shortest node-disjoint paths in hypercubes with applications

On the fault-diameter of the star graph

Node-to-set vertex disjoint paths in hypercube networks

Combinatorial Algorithms for Integrated Circuit Layout

p-MDP structure against multi-failures in high-degree node based optical networks

Digital signature-based secure node disjoint multipath routing protocol for wireless sensor networks

An efficient disjoint shortest paths routing algorithm for the the hypercube

Efficient dispersal of information for security, load balancing, and fault tolerance

Topological properties of hypercubes

An inherently stabilizing algorithm for nodeto-node routing over all shortest node-disjoint paths in hypercube networks

Topological properties of star grahs