Edge-Disjoint Spanning Trees on the Star Network with Applications to Fault Tolerance.
AbstractData communication and fault tolerance are important issues in parallel computers in which the processors are interconnected according to a specific topology. One way to achieve fault tolerant interprocessor communication is by exploiting and effectively utilizing the disjoint paths that exist between pairs of source and destination nodes. In this paper, we construct n - 1 directed edge-disjoint spanning trees, on the star network. These spanning trees are used to derive a near optimal single-node broadcasting algorithm, and fault tolerant algorithms for the single-node and multinode broadcasting, and for the single-node and multinode scattering problems. Broadcasting is the distribution of the same group of messages from one processor to all the other processors. Scattering is the distribution of distinct groups of messages from one processor to all the other processors. We consider broadcasting and scattering from a single processor of the network and simultaneously from all processors of the network. The single-node broadcasting algorithm offers a speed up of n - 1 for a large number of messages, over the straightforward algorithm that uses a single shortest path spanning tree. Fault tolerance is achieved by transmitting the same messages through a number of edge-disjoint spanning trees. The fault tolerant algorithms operate successfully in the presence of up to n - 2 faulty nodes or edges in the network. The degree of fault tolerance can be adjusted depending on the network reliability. The importance of this method lies in the fact that no prior knowledge of the faulty nodes or edges is required. All of the algorithms operate under the store-and-forward, all-port communication model.
Introduction
The star network was proposed in [1] as "an attractive alternative to the n-cube" topology for interconnecting
processors in parallel computers. Since its introduction, the network received considerable attention. Let
us denote by Vn the set of n! permutations of symbols f1; 2; :::; ng. A star interconnection network on
symbols, denoted by is an undirected graph with n! nodes. Each node
is connected to nodes that are obtained by transposing the first with the k th symbols of i, i.e.
dimensions. Thus each node is an endpoint of dimensions 2; 3; :::; n. Sn enjoys a number
of properties desirable in interconnection networks. These include node and edge symmetry, maximal fault
tolerance, and strong resilience. Because of its symmetry, the network is easily extensible, can be decomposed
in various ways and allows for simple routing algorithms. In addition Sn is superior to Cn (the n-cube) with
respect to two key properties: degree (number of edges at each node), and diameter (maximum distance
between any two nodes) [1]. The degree of Sn is sublogarithmic to the number of its nodes while a
hypercube with \Theta(n!) nodes has degree \Theta(log log n), i.e. logarithmic to the number of its nodes.
The same can be said for the diameter of Sn which is b 3(n\Gamma1)
c. The network was shown to be Hamiltonian
[24], and efficient algorithms for sorting [23] and Fourier transform computation [10, 11], were developed on
it.
Data communication and fault tolerance are important issues in multiprocessor systems, in which processors
are connected to each other according to a specific topology. In order for a network of processors to
be candidate for parallel processing, it must lend itself to the derivation of optimal communication and fault
tolerant algorithms. Working towards this direction in this paper, we construct the multiple edge-disjoint
spanning trees structure on the star interconnection network. We say that a node h of Sn is the root of
multiple edge-disjoint spanning trees, denoted by EDT h , if each of the nodes adjacent to h is the root of a
tree that spans all nodes of Sn except h and all of these trees are edge-disjoint. This structure is useful for
the construction of optimal communication and fault tolerant communication algorithms and has been used
before for other popular interconnection networks such as the hypercube [16, 18] and the cube connected
cycles [15] networks.
Using the multiple edge-disjoint spanning trees structure we derive an optimal algorithm for the single
node broadcasting problem and optimal fault tolerant algorithms for the single node broadcasting, multinode
broadcasting, single node scattering and total exchange problems under the all-port communication assumption
on Sn . Single node broadcasting is the problem where a node wishes to transmit the same message to
all other nodes. Multinode broadcasting is the problem of simultaneous single node broadcasting of the same
message from every node to all other nodes. Single node scattering is the problem of a single node sending
distinct messages to each one of the other nodes. Finally, total exchange is the problem of each node sending
distinct messages to every other node. The optimal single node broadcasting algorithm derived offers a speed
up of the straightforward algorithm that uses a single breadth first spanning tree. The basic idea
is to split the original message into packets of equal size, each of which is broadcast independently
through a different edge-disjoint spanning tree. Each node receives part of the message through a different
disjoint path from the source node and as a consequence the network resources are fully utilized. To
achieve fault tolerant communication multiple copies of the same message are send through the edge-disjoint
spanning trees. As a consequence each node receives a copy of the message through a number of disjoint
paths from the source node and the reliability of the algorithm is increased. The algorithms presented can
operate successfully in the presence of up to nodes or edges in the system. They also offer the
flexibility of controlling the degree of fault tolerance depending on the required reliability, by forcing the
same message through a specific number of edge-disjoint subtrees. As pointed out in [28], the importance
of these algorithms lies in the fact that no knowledge of the faulty nodes or edges is required in advance.
In all of the algorithms the assumption that each node can exchange messages of fixed length with all of
its neighbors at each time step, i.e. the all-port communication assumption, is adapted. Communication is
assumed to be bidirectional. Other data communication algorithms and properties on Sn can be found in
[1, 4, 5, 13, 14, 22, 25, 26, 27]. Fault tolerant algorithms and properties on Sn using different approaches
can be found in [2, 8, 9, 17, 19, 29].
This paper is organized as follows: Following the introduction to the subject in section 1, notations and
definitions that are used throughout the paper are introduced in section 2. Section 3 presents the multiple
edge-disjoint spanning trees structure on the star network. In section 4 we demonstrate several applications
of this structure in the areas of data communication and fault tolerance. More specificly, lower bounds for all
the algorithms presented are derived in subsection 4:1. The optimal single node broadcasting algorithm of M
messages under the all-port assumption is presented in subsection 4:2. Finally, the fault tolerant algorithms
for the single node broadcasting, multinode broadcasting, single node scattering and total exchange problems,
under the all-port assumption again, are presented in subsections 4:3 to 4:6 respectively. We conclude in
section 5, along with a summary of the results and some suggestions for further research.
Notations and definitions
In what follows, node i is labeled by permutation . By I n we denote the sorted permutation on the n
ng. Calligraphic letters are used for sets. We denote by N the set of symbols f1; 2; :::; ng.
Symbols i, j and h are used for nodes of Sn . By dim(i; j) we denote the dimension of edge (i; j). Two paths
between a pair of nodes are parallel if they are node (and as an extension edge) disjoint. A misplaced symbol
of a node is a symbol that does not occupy its correct position.
induced by all nodes of Sn with symbol 1, in the k th position of their
label. It is well known that S k
is an Sn\Gamma1 defined on symbols f2; :::; ng, [1]. For notation
purposes, in what follows, we use the
, to denote the set of (n \Gamma 1)! nodes of Sn with symbol 1
in the first position of their label. It is known that S 1
is a collection of (n \Gamma 1)! isolated nodes.
Definition 1: In the cycle notation of a node each symbols position is that occupied by the next symbol
(cyclically) in the cycle (the position of a symbol is defined with respect to the sorted permutation I n ) [20].
Cycles with only one symbol are excluded from the cycle notation of a node. For example node 341526 has
cycle notation (13)(245).
In what follows for node i, we denote by c i , s i , the number of cycles and the number of symbols that
belongs to those cycles, respectively, in the cycle notation of i. The minimum distance of a node i from node
I n has been shown to be [1]:
d In
ae
We now define two operations on nodes of the star network, namely the translation and the rotation
operations, that will be of primary importance for the construction of the multiple edge-disjoint spanning
trees on Sn and the description of the fault tolerant communication algorithms.
Definition 2: Consider a node h of the star network. We define T h , the translation with respect to h, of
a node i as:
(this operation is often referenced as permutation composition). By translation of a network with respect to h
we mean that each node of the network is translated with respect to h. The inverse translation with respect
to h, denoted by T
h , of a node i, is defined as:
Lemma 1: Let i, j and h represent nodes of Sn . Then (i; are edges of the same
dimension.
Proof: This becomes obvious if we analytically express (i; as:
is an edge of dimension k then (T h (i); T h (j)) is also an edge of dimension k. 2
Definition 3: Let us define the function r from N to N as:
ae
(notice that r maps f1; 2; 3; ng to f1; 3; 4; :::; n; 2g). The rotation of a node i 2 Sn , denoted by R,
is defined as:
or equivalently i
applications of rotation. By
rotation of a network we mean that rotation is applied to each node of the network.
Lemma 2: Let i and j be nodes of Sn and i be the nodes obtained from i and j,
respectively, by application of a rotation:
1. If (i; j) is an edge of dimension k, is an edge of dimension r(k). As an
extension to this, the edges obtained after applications of rotation on (i; dimensions
respectively. With this observation we conclude that the each
obtained as a rotation of its previous one, are all of different dimensions.
2. If i
.
3. The rotation operation preserves the distance between nodes of Sn , or equivalently, d In In (i 0 ).
Proof: We'll prove each part separately:
1. If we analytically express (i;
we notice that if (i; j) is an edge of dimension k, then (i is an edge of dimension r(k). This is true
because from the definition of rotation the position of symbol r(i k ) in i 0 is r(k).
2. If i
1. From the definition of r, if i
As a result
.
3. We must prove the following: (a) if
(c) c From part 2 of this lemma (a) is easily derived. We know from the definition of rotation
that
This means that if symbol i k occupies position k in i then symbol r(i k ) occupies
position r(k) in i 0 . As a consequence if cycle (i k1
belongs to the cycle notation of i then
cycle (r(i k1 ); r(i k2 ); :::; r(i k l
belongs to the cycle notation of i 0 and we conclude that s
To summarize, the translation and the rotation operations preserve the distance between nodes of Sn .
The rotation operation maps every edge in dimension d to an edge in dimension
Application of rotation k times, or R k , maps every edge in dimension d to an edge in dimension r k
2. The translation operation preserves the dimension of every edge. Finally the
topology of Sn , or a subgraph of Sn , remains unchanged under translation or rotation.
Definition 4: A group of nodes for which each one is derived from its previous one by application of a
rotation is called a necklace
Lemma 3: Necklaces have the following properties:
1. Each node i 2 S k
belongs to a necklace that includes nodes.
2. Each node i
belongs to a necklace that includes at most n \Gamma 1 distinct nodes.
3. All nodes of a necklace have the same minimum distance from I n .
Proof: We prove each part separately.
1.
1. From the definition of r, the nodes derived from i by
consecutive rotations have first symbols 1. So the nodes that belong to
a necklace of this type start with different symbols and as a consequence are different. Also a necklace
of this type contains exactly nodes. From the definition of r, it is true that r
produced by i after rotations then i 0
that
For example node 4123 of S 4 belongs to necklace ( 4123; 2413; 3421 ).
2. Node i
1. From the definition of r, all nodes derived from i by consecutive rotations
start with symbol 1. If i 0 is produced by i after rotations then i 0
we conclude that However it is possible that
For example node 13254 of S 5 is mapped to itself after only two and not applications of
rotation, R 2 belongs to a necklace that contains only two nodes ( 13254; 15432 ),
while node 12435 belongs to a necklace that contains
3. From part 3 of lemma 2 this is easily derived. 2
From part 3 of lemma 3 we conclude that the nodes of Sn at each distance from I n are grouped into
necklaces. For example, the necklaces of S 4 at each distance from I 4 are given below enclosed in parentheses:
The size of a necklace of Sn is always a divisor of n \Gamma 1.
Definition 5: An unfolded necklace is a group of exactly nodes, each obtained as a rotation
of its previous one. Unfolded necklaces can contain the same node more than once. For example
is an unfolded necklace of S 5 .
The definitions of the rotation operation and the necklace will be of primary importance for the construction
of the multiple edge-disjoint spanning trees and for the description of the fault tolerant algorithms
on Sn . Both of these definitions have been developed in analogy to definitions with similar properties that
exist for the hypercube interconnection network. The application of rotation on a node of Sn is analogous
to the application of a right cyclic shift operation on a node of the hypercube. The definition of necklace for
nodes of Sn is analogous to similar groups defined for nodes of the hypercube in [18]. The term necklace was
initially used in [21] for similar groups of nodes in the shuffle-exchange graph. An interesting observation is
that although the definitions in [18] were motivated by specific properties of the hypercube topology, similar
definitions, with the same properties, can be derived for other networks, like the star network, which has a
structure that is fundamentally different from that of the hypercube.
(b)
(a)
shortest
path tree
on S 2
shortest
path tree
on S 3
shortest
path tree
on S n

Figure

2: (a) A schematic representation of SPT In . (b) The SPT I4 .
3 Construction of the multiple edge-disjoint spanning trees
We say that node h of Sn is the root of multiple edge-disjoint spanning trees, denoted by EDT h , if each of
the nodes adjacent to h is the root of a tree that spans all nodes of Sn except h and all of these trees are
edge-disjoint. In this section we construct EDT In rooted at node I n of Sn . The EDT h , rooted at any other
node h of Sn , will be obtained by applying the operation of translation with respect to h on EDT In
Before we proceed to the construction of the EDT In , we construct a balanced shortest path tree, rooted
at node I n , that includes all nodes of S k
In . For the definition of the SPT In
we need the following: Denote by C k , 1 - k - n, the set of dimensions f2; 3; :::; ng \Gamma fkg (C 1 is the set of
dimensions f2; 3; :::; ng). Assume node i 2 S k
n. If we move from i along any of the dimensions
in C k , the resulting node belongs to the same substar S k
that i belongs. We split C k into two subsets
is the first misplaced symbol cyclically
to the right of symbol 1 in i (excluding
;; otherwise
and C 2
k;i . Also let be such that i p i
is the first misplaced symbol
cyclically to the right of symbol 1 in i (excluding
In what follows the k th subtree of a spanning tree ST h rooted at node h, is defined to be the subtree
rooted at the neighbor of h over dimension k, and is denoted by T STh
k .
Definition 6: The shortest path tree SPT In rooted at node I n of Sn is defined through the following
parent and children functions:
parent SPT (i; I n
ae
children SPT (i; I n
It can be easily seen that the parent SPT and children SPT functions are consistent. A schematical representation
of SPT In along with SPT I4 can be seen in Fig. 2.
Lemma 4: The SPT In has the following characteristics:
1. All nodes of S k
k .
2. It is a shortest path tree.
Proof: We prove each part separately.
1. We'll prove that if i
also belongs to S k
node adjacent to I n in which case its parent is I n . To show this we must prove that p i 6= k for all nodes
that are not adjacent to I n , which is true from the definition of p i . If
is such that i p i
is the first misplaced symbol cyclically to the right of symbol 1 (position
in i, excluding symbol i 1 . In this case p if the only misplaced symbols in i are symbols
and which concludes that node i is adjacent to I n .
2. We'll prove that if i
In (i p i
In (i) \Gamma 1, or that the parent of each node
in SPT In is closer to I n than the node itself. This can be verified from a close look to the definition of
and the first symbol of i is moved to its correct position. If
such that i p i
is the first misplaced symbol (excluding cyclically to the right of symbol 1 in i, which
has the effect of merging cycle (1k) with the cycle that includes symbol p i in the cycle notation of i.
From the definition of d In the above follows. 2.
We now extend the definition of SPT In , to include nodes of S 1
. SPT In is extended so that each one
of its nodes has a child that belongs to S 1
(except nodes that are adjacent to I n ). The resulting structure
is no more a spanning tree but a directed graph denoted by SPG In .
Definition 7: The shortest path graph SPG In , rooted at node I n of Sn is defined through the following
parent and children functions. By parent SPG (i; l; I n ) and children SPG (i; l; I n ), we denote the parent and
children nodes, respectively, of node i in subtree T SPG I n
l .
parent SPG (i; l; I n
ae
parent SPT (i; I n ); if
children SPG (i; l; I n
children SPT (i; I n ); if or i is adjacent to I n ;
children SPT (i; I
but i is not adjacent to I n ;
It can be easily seen that the parent SPG and children SPG functions are consistent. The SPG I4 can be
seen in Fig. 3.
Lemma 5: The SPG In has the following characteristics:
1. Each node of S 1
times in SPG In , once in each of the subtrees T SPG I n
l ,
2. For each i
parallel paths that lead to node I n through SPG In , and these
paths have minimum lengths [8].
Proof: We prove each part separately.
1. According to the definition of parent SPG , each node i
I n is connected to T SPG I n
l
through dimension l.

Figure

3: The SPG I4 .
2. Node i
is connected to subtree T SPG I n
l l, to node i
. From lemma 4, i 0 is connected with a shortest path to I n through subtree
l that includes only nodes of S l
. As a consequence, these paths are parallel since the path
through the l th subtree includes only nodes of S l
. Using this type of reasoning it has been proven
in [8] that these paths have minimum lengths. 2
Up to this point only nodes of S 1
belong to all subtrees T SPG I n
l , 2 - l - n. However nodes of any
other S l
only to subtree T SPG I n
l . Now we further extend SPG In so that each subtree
includes all nodes i 2 S l
n. The resulting structure will be the multiple edge-disjoint spanning
trees, denoted by EDT In . In order for the subtrees to be edge-disjoint, each node should be connected to
each subtree through a different neighboring node and as an extension through a different one of its incident
edges. Let us remind that node i 2 S l
connected to its parent in the l th subtree through
neighbor
Definition 8: The EDT In rooted at node I n of Sn is now defined through the following parent and
children functions. By parent EDT (i; l; I n ) and by children EDT (i; l; I n ), we denote the parent and children
nodes, respectively, of node i in subtree T EDT I n
l . For clarity of definition we distinguish among different
kinds of nodes:
1.
(the parent of i in SPG In starts with symbol k). Node i
is connected to subtree T EDT I n
through neighbor 1i 2 :::i n , and to any other subtree T EDT I n
l , l
li 2 :::i n . For example node 3124 of Sn is connected to subtree T EDT I 4through neighbor 1324, and to subtree T EDT I 4
4 through neighbor 4123.
parent EDT (i; l; I n

Figure

4: The EDT I4 .
2. Node i
starts with symbol k). Node i is connected to subtree
through neighbor 1i 2 :::i n , and to any other subtree T EDT I n
l , l
neighbor li 2 :::i n . For example node 2143 of S 4 is connected to subtree T EDT I 4
4 through neighbor 1243,
and to subtree T EDT I 4
3 through neighbor 3142.
parent EDT (i; l; I n
li
children EDT (i; l; I n
is adjacent to I n ,
not adjacent to I n ,
3. Node i
its parent in SPG In start with
connected to subtree T EDT I n
through neighbor 1i 2 :::i n , and to subtree T EDT I n
through neighbor ki 2 :::i n . To any other subtree T EDT I n
l , l
, l 6= k, it is connected through
neighbor li 2 :::i n . For example node 4123 of S 4 is connected to subtree T EDT I 4
4 through neighbor 1423,
and to subtree T EDT I 4
3 through neighbor 2143.
parent EDT (i; l; I n
4. Node i
(nodes that start with symbol 1).
parent EDT (i; l; I n ng (11)
children EDT (i; l; I n ng [
;; otherwise
5. Finally, the parent and children nodes of I n are:
parent EDT
children EDT
The parent EDT and children EDT functions that define EDT In are consistent. The EDT I4 can be seen in
Fig. 4. Notice that each edge belongs twice in EDT In , once in each direction, since communication is
bidirectional.
Lemma The EDT In has the following characteristics:
1. Subtrees T EDT I n
l , 2 - l - n, are all edge-disjoint.
2. Subtree T EDT I n
r(l) is a rotation of subtree T EDT I n
l (its previous subtree cyclically).
3. For each node i 2 S k
parallel paths of almost minimum lengths that lead
to node I n through EDT In .
4. The depth of EDT In is at most b 3(n\Gamma1)
Proof: See Appendix. 2
The multiple edge-disjoint spanning trees, EDT h , rooted at any other node h of Sn can be obtained from
In , using the operation of translation with respect to h (see definition 1). Node i of Sn is connected to
its parent, children nodes in subtree T EDTh
l along the same dimensions that node T \Gamma1
h (i) is connected to its
parent, children nodes in subtree T EDT I n
l . This is easily derived because connectivity and the dimension of
each edge are preserved under translation in Sn (lemma 1).
We need to pose an ordering to the children of each node in each of the subtrees T EDT I n
This will be useful in the construction of the algorithms described in the following section. We define the k th
ordering of numbers f2; 3; :::; ng, denoted by OE k to be such
k. Each node arranges its children in each subtree T EDT I n
k according to the k th ordering of the
dimensions of the edges it is connected to them. This guarantees that if node i is connected to its children
in subtree T EDT I n
k through dimensions c l in order, then node R(i) is connected to its children in
subtree T EDT I n
dimensions r(c 1 ); r(c 2 ); :::; r(c l ) again in order. This ordering in combination with
the fact that subtrees T EDT I n
are rotations of each other guarantees that corresponding nodes
of the subtrees form unfolded necklaces. For example the nodes enclosed in rectangulars of the same kind in
Fig. 4 form unfolded necklaces. Also corresponding edges of the subtrees are rotations of each other and as
consequence all of different dimensions (lemma 6). For example the dotted edges in Fig. 4 are rotations of
each other and of different types. The ordering is carried by translation to EDT h rooted at any other node
h of Sn .
Applications
The multiple edge-disjoint spanning trees structure, defined in the previous section is used to derive optimal
communication and fault tolerant communication algorithms on the star network. More specificly we derive
an optimal single node broadcasting algorithm. We also derive optimal fault tolerant algorithms for four
basic communication problems in interconnection networks, namely the single node broadcasting, multinode
broadcasting, single node scattering and total exchange problems. All of the algorithms operate under the
all-port communication assumption. Before we proceed to the description of the algorithms, we derive lower
bound for the time and the number of message transmissions required for each of them.
4.1 Lower Bounds
Broadcasting on an interconnection network is the problem where a node wishes to send the same message to
all other nodes in the network. To broadcast M messages from a node of Sn , by pipelining the communication
from the root towards the leaves along any b 3(n\Gamma1)
first spanning tree, under the allport
communication assumption, the number of time steps required is which is not
optimal. Since Sn is a regular network with degree the lower bound for the single node broadcasting
algorithm of M messages assuming all ports of a node can be used simultaneously for message transmission
is d M
To achieve this lower bound the M messages are grouped into packets of
equal size, each of which is communicated over a different edge of the source node and is pipelined down
a different edge-disjoint subtree rooted at a node adjacent to the source node. Since each node receives
each of the M messages once, the minimum number of message transmissions required for an optimal single
node broadcasting algorithm is M (n! \Gamma 1). In the fault tolerant single node broadcasting algorithm the M
messages are pipelined down each one of the of the spanning trees rooted at the nodes
adjacent to the source node. The time required for this algorithm is M
each node receives
each of the M messages through parallel paths, the minimumnumber of message transmissions required
is
Multinode broadcasting on an interconnection network is the problem where each node of the network
wishes to send a message to all other nodes. If each node wishes to broadcast M messages, then each node
must receive a total of M (n! \Gamma 1) messages. As a consequence the minimum number of message transmissions
required is Mn!(n! \Gamma 1). Under the all-port assumption all edges of the network can be used for
message transmissions at each time step. Thus the minimum time required for the algorithm to complete
is d M(n!\Gamma1)
e. The lower bounds for the fault tolerant multinode broadcasting algorithm are easily derived
from the lower bounds for the multinode broadcasting with a multiplication by factor n \Gamma 1.
Single node scattering on an interconnection network is the problem where a node wishes to send a
different message to each one of the other nodes. If the source node wishes to send M messages to each one
of the other nodes, M (n! \Gamma 1) different messages must be transmitted by the source node. Under the all-port
assumption all the incident to the source node can be used for message transmissions at each
time step and as a consequence the minimum time required for the algorithm to complete is d M(n!\Gamma1)
e. The
number of message transmissions required can be found as follows: A message destined to a specific node
must travel as many edges as the shortest distance from the source to this node. If we sum the shortest
distances from the source to each node, this will be the minimum number of message transmissions required
for this problem:
is the number of nodes at a distance k from the source and d has been shown to be [3]:
Hn is the n th harmonic number:
n . Thus the minimumnumber of message transmissions
required for a single node scattering algorithm on Sn is:
In the fault tolerant single node scattering algorithm the source node transmits the M (n! \Gamma 1) messages to all
of its neighbors simultaneously. Each of the spanning trees rooted at the nodes adjacent
to the source node are used for a single node scattering algorithm. The number of message transmissions
required is
1). Since the source node must transmit
messages the time required for this algorithm is M (n! \Gamma 1).
Total exchange on an interconnection network is the problem where each node wishes to send a distinct
message to every other node, in other words, every possible pair of nodes exchange distinct messages. The
fault tolerant total exchange algorithm is equivalent to n! different fault tolerant single node scattering
algorithms, one from each node of Sn . Thus the minimum number of message transmissions required is
1). Under the all-port assumption n!(n \Gamma 1) edges can be
used for message transmission at each time step simultaneously. Thus the minimum time required for the
algorithm to complete is M
All the lower bounds were derived for degree of fault tolerance 2. This means that each node receives
each message through paths. The lower bounds for the algorithms with controlled degree of
fault tolerance will be derived in the following sections along with the description of the algorithms.

Table

below summarizes the lower bounds for all of the above problems, with degree of fault tolerance
messages transmitted to each node. By t n we denote the quantity n!(n
problem time number of transmissions
single node broadcasting d M
fault tolerant single node broadcasting M
fault tolerant multinode broadcasting M
fault tolerant single node scattering M

Table

1: Lower bounds on the star network.
The algorithms derived here for all of the above problems are optimal in terms of time and number of
message transmissions. Some of the methods used in this sections to derive lower bounds for the communications
problems under consideration are similar to the methods used in [7] to derive lower bounds for
similar problems on the hypercube network.
4.2 Optimal single node broadcasting
In a single node broadcasting algorithm one node wishes to transmit a single message or a group of messages to
each other node. To broadcast M messages from a node of Sn , by pipelining the communication from the root
towards the leaves along any b 3(n\Gamma1)c depth, breadth first spanning tree, under the all-port communication
assumption, the number of time steps required is
which is not optimal. Since Sn is a
regular network with degree the lower bound for the single node broadcasting algorithm of M messages
assuming all ports of a node can be used simultaneously for message transmission is d M
2 c. This
lower bound can be achieved if the M messages are grouped into packets, each of size M
. Each of
the packets is communicated over a different edge of the source node h and is pipelined down a different
edge-disjoint subtree of the EDT h rooted at the source node. As soon as a node receives a message from
its parent node in subtree T EDTh
copy, and forwards the message to its children
nodes in the same subtree. The result is that each node receives each of the packets of the message
through a different parallel path from the source node. The time required for this algorithm to complete is
at most d M
which is almost optimal, since the depth of the multiple edge-disjoint spanning
trees structure is at most b 3(n\Gamma1)
4. The number of message transmissions required for the algorithm is
since each node receives each of the M messages once, which is the minimum possible. Using
this algorithm the resources of the network are fully utilized since all communication edges contribute to the
distribution of the information.
4.3 Fault tolerant single node broadcasting
The multiple edge-disjoint spanning trees structure can be used to derive a fault tolerant single node broadcasting
algorithm under the all-port communication assumption. Assume that the source node h, wishes to
broadcast M messages to all the other nodes. Node h sends the messages it wishes to broadcast through
all its incident edges simultaneously and these are pipelined down each of the
rooted at the nodes adjacent to h. As soon as a node receives a message from its parent node in subtree
and forwards the message to its children nodes in the same subtree. Using
this algorithm each of the nodes of Sn receives the same message through paths. If up to
node or edge faults occur in the system that block the message from passing we are still guaranteed that each
node receives a copy of the message and as a consequence the algorithm is tolerant. If we assume
that the system has faults that alter the contents of the messages instead of just blocking or destroying it,
the fault tolerance degree of the algorithm decreases since an election algorithm is required at each node in
order to select the intact message. A brief discussion on the election algorithms can be found in [28]. The
time required for this algorithm to complete using the multiple edge-disjoint spanning trees structure is at
most
which is almost optimal, since the depth of the multiple edge-disjoint spanning trees
is at most b 3(n\Gamma1)
4. The number of message transmissions required is since each node
receives each of the M messages which is the minimum possible.
Using a similar technique we can control the degree of fault tolerance of the single node broadcasting
algorithm. Assume that the required degree of fault tolerance is 2. This means that each node
must receive each message through x parallel paths, or in other words that each message must be pipelined
down at least x edge-disjoint subtrees rooted at the nodes adjacent to the source node. However the number
of available edge-disjoint subtrees is n \Gamma 1. In order to achieve maximum utilization of the network resources
the M messages are grouped into
x packets, each of size M
(n\Gamma1)=x
must divide this to
work properly). Each of the
x packets is pipelined down x edge-disjoint subtrees. As a consequence, all
of the
subtrees are used for message transmission. The result is that
each node receives each of the
x packets through x of its incident edges, and as an extension through
x parallel paths from the source node, and as a consequence the fault tolerance degree of the algorithm is
1. The time required for the algorithm is at most Mx
which is almost optimal, since
the depth of the multiple edge-disjoint spanning trees is at most b 3(n\Gamma1)
4, and in addition we have
the flexibility of controlling the degree of fault tolerance based on how reliable the system is. The number
of message transmissions required is M (n! \Gamma 1)x which is again optimal, since each node receives each of
the M messages x times. To illustrate the algorithm assume that node 12345 of S 5 , which is the root of
whishes to broadcast messages with degree
of fault tolerance means that up to one faulty node or edge should be tolerated by the
algorithm). The message of size M is split into
each of size Mx
2. Each
of the packets is pipelined down
5 . As a consequence, each node receives each packet through two parallel paths and the fault
tolerance degree of the algorithm is one.
4.4 Fault tolerant multinode broadcasting
In a multinode broadcasting algorithm, each node wishes to transmit a single message, or a group of messages
to each one of the other nodes. As a consequence each of the nodes should be the root of multiple edge-disjoint
spanning trees. The EDT In can be replicated at any other node h of Sn using the operation of
translation with respect to h, as it was explained at the end of section 3 (see definition 1). Fault tolerance
can be achieved if each node receives each message through paths. However in this case we
have to guarantee that no conflicts arise during the execution of the algorithm, since all nodes are sources of
messages. Under the all-port assumption are available on Sn at each time step for message
transmission. This means that the messages originating from a specific node should be transmitted through
at most n \Gamma 1 edges, at each time step. Let us denote by L k (h) the set of edges on which messages originating
at node h are transmitted at time step k of the algorithm. For each k, L k (h) is obtained from L k using
the operation of translation with respect to h (if (i; definition
1). The following lemma is enough to guarantee that no conflicts arise during the execution of the algorithm.
Lemma 7: If for each k, the edges in L k are all of different dimensions, then for each k, the sets
ranges over all nodes of Sn , are disjoint.
Proof: Assume two different edges (i; and take the edges (T h (i); T h (j)) 2
are obtained by (i; respectively, under translation
with respect to two different nodes of Sn , h and h 0 . Also assume that (T h (i); T h
Since the dimension of each edge is preserved under translation (lemma 1), this means that dim(i;
our assumption that (i; j) and
are two different edges of L k (I n ). 2
The fault tolerant multinode broadcasting algorithm on Sn , assuming each node wishes to broadcast M
messages, proceeds as follows:
1. Each source node sends the M messages it wishes to broadcast to all of its neighbors simultaneously.
2. As soon as a node receives a group of M messages from its parent in subtree T EDTh
k , it saves a copy,
and forwards the messages to its leftmost child in the same subtree. However, if the node is a leaf of
subtree T EDTh
k , it sends an acknowledgement to its parent node in the subtree.
3. When a node receives an acknowledgement from one of its children nodes in subtree T EDTh
k , it forwards
the M messages it received from its parent in this subtree to its next child node in the subtree. However,
if the node has no more children in this subtree, it sends an acknowledgement to its parent node in the
subtree.
The algorithm terminates when each source node receives acknowledgements from all its neighbors. This
algorithm corresponds to a depth first traversal of the edges in each of the edge-disjoint subtrees. This means
that at each time step of the algorithm corresponding edges of the subtrees, T EDTh
rooted at
the nodes adjacent to h, are used simultaneously for message transmission. Since corresponding edges of the
subtrees of EDT In are all rotations of each other, they are all of different dimensions (lemma
the requirement of lemma 7 for conflict avoidance is satisfied by the algorithm.
The time required for this algorithm to complete is M (n! \Gamma 1) which is optimal. The number of message
transmissions required is which is the minimum possible, since each node receives each of
the times. The way the algorithm was constructed, the degree of fault tolerance
is which means that each message is transmitted through all of the edge-disjoint subtree rooted at
the nodes adjacent to each source node. Controlling the degree of fault tolerance is possible by a technique
similar to the one described in subsection 4.3.
4.5 Fault tolerant single node scattering
In a single node scattering algorithm one node wishes to transmit distinct messages to each one of the other
nodes. The single node scattering algorithm on Sn , under the all-port assumption, can become fault tolerant
using the multiple edge-disjoint spanning trees. A message destined to a specific node is transmitted through
each of the edge-disjoint subtrees rooted at the nodes adjacent to the source node. In each subtree, messages
destined to nodes that are the furthest from the source are transmitted first.
If each node is the destination of M messages, the time required for this algorithm to complete is M (n!\Gamma1),
which is optimal, since each edge incident to the source node constitutes a bottleneck for M (n! \Gamma 1) messages.
The number of message transmissions required is which is asymptotically
optimal, because the lengths of the between two nodes of Sn are not all equal the length
of a shortest path between the two nodes [8]. Controlling the degree of fault tolerance is possible using a
technique similar to the one described in subsection 4.3.
4.6 Fault tolerant total exchange
In a total exchange algorithm each node wishes to transmit distinct messages to each other node. As a
consequence, each of the nodes should be the root of multiple edge-disjoint spanning trees. The EDT In can
be replicated at any other node h of Sn using the operation of translation with respect to h (see definition
1). Fault tolerance can be achieved if each node receives each message through paths. As in
the fault tolerant multinode broadcasting algorithm, we have to guarantee that no conflicts arise during the
execution of the algorithm, since all nodes are sources of messages, or in other words we have to guarantee
that the requirement of lemma 7 is satisfied.
The way node I n transmits the messages through the edge-disjoint subtrees rooted at its neighbors is the
following: For each node i of Sn , I n sends the messages destined to nodes R k\Gamma2 (i), 2 - k - n, respectively
through subtrees T EDT I n
As soon as a group of messages reaches its destination
another group is send from I n . Nodes R k\Gamma2 (i), 2 - k - n, form an unfolded necklace of nodes (see definition
5) at a specific level of EDT In , since subtrees T EDT I n
rotations of each other (lemma
6). As a consequence the that lead from I n to nodes R k\Gamma2 (i), 2 - k - n, respectively through
subtrees T EDT I n
rotations of each other. This means that the edges at each level
of the paths are of different dimensions and the requirement of lemma 7 for conflict avoidance is satisfied. If
at a specific instance of the algorithm node I n transmits messages to nodes R k\Gamma2 (i), 2 - k - n, respectively
through subtrees T EDT I n
simultaneously, then any other node h of Sn transmits messages to
nodes T h (R k\Gamma2 (i)), 2 - k - n, respectively through subtrees T EDTh
simultaneously. This is a
simple application of the operation of translation with respect to h.
If M messages must be transmitted to each node from each other node the time required for the algorithm
to compete is M (n! \Gamma 1) +O(M t n ) which is asymptotically optimal. The number of message transmissions
required is which is again asymptotically optimal. This algorithm
is only asymptotically optimal because the lengths of the between two nodes of Sn
are not all equal to the length of a shortest path between the two nodes [8]. The way the algorithm was
described the degree of fault tolerance is which means that each message is transmitted through each
different edge-disjoint subtree rooted at the nodes adjacent to each source node. Controlling the degree of
fault tolerance is possible by a technique similar to the one described in subsection 4.3.
Conclusions
We presented several algorithms on the star interconnection network, in the areas of data communication
and fault tolerance. New definitions like that of the rotation operation and the necklace for nodes of Sn were
introduced to facilitate the construction of multiple edge-disjoint spanning trees on Sn . As a result a multiple
edge-disjoint spanning trees structure of optimal depth was constructed on the star interconnection network.
Using this structure an optimal single node broadcasting algorithm and optimal fault tolerant algorithms for
the single node broadcasting, multinode broadcasting, single node scattering and total exchange problems
on the star network were presented. All of the algorithms operate under the all-port assumption and are
optimal in terms of time and number of message transmissions. Constructing multiple edge-disjoint spanning
trees on the star network that would offer optimal solutions to the above problems under the assumption
that each node can exchange a message of fixed length with only one of its neighbors at each time step, i.e.
the one-port communication assumption, is a problem that remains open.
We now provide a comparison of the algorithms presented in this paper for the four communication
problems under consideration on the star network, with algorithms for the same problems, under exactly the
same assumptions, on the popular hypercube network. Tables 2 and 3 below give the number of message
transmissions and the communication time required for each of the problems on the Sn and the hypercube
network of dimension k, denoted by C k , respectively. For the fault tolerant communication algorithms the
degree of fault tolerance is assumed to be x.
problem time number of transmissions
single node broadcasting d M
fault tolerant single node broadcasting d Mx
fault tolerant multinode broadcasting d Mx(n!\Gamma1)
fault tolerant single node scattering d Mx(n!\Gamma1)
fault tolerant total exchange d Mx(n!\Gamma1)

Table

2: Lower bounds on the star network of dimension n.
problem time number of transmissions
single node broadcasting d M
fault tolerant single node broadcasting d Mx
fault tolerant multinode broadcasting d Mx(2 k \Gamma1)
fault tolerant single node scattering d Mx(2 k \Gamma1)
fault tolerant total exchange d Mx(2 k \Gamma1)

Table

3: Lower bounds on the hypercube network of dimension k.
In table 4 below the performances of the two networks are compared. Since the star network is defined
for numbers of nodes which are factorials, while the hypercube is defined for powers of two, the comparison
cannot be exact. In the comparison below a hypercube network with O(2 k nodes and degree
log n) is assumed.
From table 4 we notice that whenever the performance of an algorithm depends on the degree of the
network, as for example the communication times of the fault tolerant multinode broadcasting, single node
scattering and total exchange algorithms, the hypercube network performs better than the star network by
a factor of log n. On the other hand, whenever the performance of an algorithm depends on the diameter
of the network, or the lengths of the shortest paths between nodes, as for example the number of message
transmissions of the fault tolerant single node scattering and total exchange algorithms, the star network
performs better by a factor of log n. The communication times of the single node broadcasting and the fault
tolerant single node broadcasting algorithms depend on both the degree and the diameter of the networks
and this is reflected at the comparison of their performances. In any other case the performance of the two
networks is the same. However we should not forget that the star network has smaller degree resulting in
processors with a smaller number of ports and as a consequence smaller cost.
problem net time number of transmissions
single node broadcasting Sn O( M
fault tolerant single node broadcasting Sn O( Mx
Cn O( Mx
fault tolerant multinode broadcasting Sn O( Mxn!
Cn O( Mxn!
fault tolerant single node scattering Sn O( Mxn!
Cn O( Mxn!
fault tolerant total exchange Sn O( Mxn!
Cn O( Mxn!

Table

4: Comparison of star and hypercube performances.



--R

"The Star Graph: An Attractive Alternative to the Hypercube"
"The Fault Tolerance of Star Graphs"
"A Group Theoretic Model for Symmetric Interconnection Net- works"
"A Novel Routing Scheme on the Star and Pancake Networks and its Applica- tions"

Parallel and Distributed Computation: Numerical Methods
"Optimal Communication Algorithms for Hypercubes"
"A Comparative Study of Topological Properties of Hypercubes and Star Graphs,"
"Three Disjoint Path Paradigms in Star Networks"
"Parallel Algorithms for the Fourier and Other Mathematical Transforms,"
"A Parallel Algorithm for Computing Fourier Transforms on the Star Graph,"
"Optimal Communication Algorithms on the Star Interconnection Net- work"
"Optimal Communication Algorithms on Star Graphs Using Spanning Tree Constructions"
"Methods and Models of Communication in Usual Networks"
"Arc Disjoint Spanning Trees on Cube Connected Cycles Network"
"Fault-tolerant Gossiping on Hypercube Multicomputers"
"Fault Tolerant Routing in the Star and Pancake Interconnection Network"
"Optimum Broadcasting and Personalized Communication in Hypercubes"
"Characterization of Node Disjoint (parallel) Paths in Star Graphs"
The Art of Computer Programming
Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange and Other Net- works
"Optimal Broadcasting on the Star Graph"
"An Efficient Sorting Algorithm for the Star Graph Interconnection Net- work"
"Embedding Hamiltonians and Hypercubes in Star Inter-connection Graphs"
"Data Communication and Computational Geometry on the Star and Pancake Networks"
"On the Tree Structure of the Star Graph"
"On the Properties of Breadth First Spanning Tree of the Star Graph"
"Reliable Broadcast in Hypercube Multicomputers"
"A Fault Tolerance Routing Algorithm in Star Graphs"
--TR

--CTR
Abderezak Touzene, Optimal all-ports collective communication algorithms for the k-ary n-cube interconnection networks, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.4, p.221-231, March 2004
Abderezak Touzene , Khaled Day , Burkhard Monien, Edge-disjoint spanning trees for the generalized butterfly networks and their applications, Journal of Parallel and Distributed Computing, v.65 n.11, p.1384-1396, November 2005
Satoshi Fujita, A Fault-Tolerant Broadcast Scheme in the Star Graph under the Single-Port, Half-Duplex Communication Model, IEEE Transactions on Computers, v.48 n.10, p.1123-1126, October 1999
Cheng-Kuan Lin , Hua-Min Huang , Lih-Hsing Hsu, The super connectivity of the pancake graphs and the super laceability of the star graphs, Theoretical Computer Science, v.339 n.2, p.257-271, 12 June 2005
N. W. Lo , Bradley S. Carlson , D. L. Tao, Fault Tolerant Algorithms for Broadcasting on the Star Graph Network, IEEE Transactions on Computers, v.46 n.12, p.1357-1362, December 1997
Chin-Tsai Lin, Embedding k(n - spanning trees in arrangement graphs, Journal of Parallel and Distributed Computing, v.63 n.12, p.1277-1287, December
Satoshi Fujita, Neighborhood Information Dissemination in the Star Graph, IEEE Transactions on Computers, v.49 n.12, p.1366-1370, December 2000
Chi-Chang Chen , Jianer Chen, Nearly Optimal One-to-Many Parallel Routing in Star Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1196-1202, December 1997
Shan-Chyun Ku , Biing-Feng Wang , Ting-Kai Hung, Constructing Edge-Disjoint Spanning Trees in Product Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.213-221, March
Adele A. Rescigno, Optimally Balanced Spanning Tree of the Star Network, IEEE Transactions on Computers, v.50 n.1, p.88-91, January 2001
Abderezak Touzene, Edges-disjoint spanning trees on the binary wrapped butterfly network with applications to fault tolerance, Parallel Computing, v.28 n.4, p.649-666, April 2002
communication algorithm;interconnection network;spanning tree;edge-disjoint trees;parallel algorithm;star network;fault tolerance