Title :
Sparse networks tolerating random faults for tree-like and butterfly-like networks
Author :
Nomura, Kumiko ; Yamada, Toshinori ; Ueno, Shuichi
Author_Institution :
Dept. of Commun. & Integrated Syst., Tokyo Inst. of Technol., Japan
Abstract :
A network G* is called an RFT (random-fault-tolerant) network for a network G if G* contains a fault-free isomorphic copy of G with high probability even if processors fail independently with constant probability. This paper shows that if G is an N-processor partial k-tree, butterfly, wrapped butterfly, or Benes network then we can construct an RFT networks for G with O(N) processors and O(N log N) communication links
Keywords :
fault tolerant computing; graph theory; multiprocessor interconnection networks; probability; Benes network; N-processor partial k-tree network; butterfly-like networks; fault-free isomorphic copy; probability; random faults; random-fault-tolerant network; sparse networks; tree-like networks; wrapped butterfly network; Fault tolerant systems; Hypercubes; Multiprocessing systems; Multiprocessor interconnection networks; Tree graphs;
Conference_Titel :
Circuits and Systems, 2000. IEEE APCCAS 2000. The 2000 IEEE Asia-Pacific Conference on
Conference_Location :
Tianjin
Print_ISBN :
0-7803-6253-5
DOI :
10.1109/APCCAS.2000.913641
