Fault tolerant communication algorithms on the star network using disjoint paths
Paraskevi Fragopoulou, Selim G. Akl · 2002
One way to achieve fault-tolerant communication on interconnection networks is by exploiting and effectively utilizing the disjoint paths that exist between pairs of source and destination nodes. We construct a graph that consists of n-1 directed edge-disjoint spanning trees on the star network. This graph is used to derive fault-tolerant algorithms for the single-node and multinode broadcasting, and for the single-node and multinode scattering problems under the all-port communication assumption. Fault tolerance is achieved by transmitting the same messages through a number of edge-disjoint spanning trees. These algorithms operate successfully in the presence of up to n-2 faulty nodes or edges in the network.>