A fault-tolerant reconfiguration scheme in the faulty star graph

In this paper, we propose a scheme to identify the maximal fault-free substar-ring. This is the first attempt to derive a reconfiguration scheme with high processor utilization in the faulty n-star graph. The maximal fault-free substar-ring is connected by a ring of fault-free virtual substrate and the maximal length of the ring is n(n - 1)(n - 2). Our posed scheme can tolerate n - 3 faults such that the processor utilization is n(2) - 2n +3/n(2) - n This is a near optimal result since the maximal fault-free substar-ring is constructed using all of the possible fault-free (n - 2)-substars. Moreover, our algorithm can still work when the number of faults exceeds n - 3. The simulation results also show that the processor utilization is more than 50% if the number of faults is less than n(2) - n - 1/2 2 in the n-star graph.