A Fault-Tolerant Reconfiguration Scheme in the Faulty Star Graph
Yuh‐Shyan Chen, Jang‐Ping Sheu · 2000
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 substars and the maximal length of the ring is n(n- 1)(n- 2). Our pro-2 n − 2n+ 3 posed scheme can tolerate n- 3 faults such that the processor utilization is 2 n − 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 2 utilization is more than 50 % if the number of faults is less than n −n − 1 in the n-star graph. 2