DocumentCode
2999603
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
fYear
2000
fDate
2000
Firstpage
799
Lastpage
802
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/APCCAS.2000.913641
Filename
913641
Link To Document