Title :
Fault-tolerant communication algorithms in toroidal networks
Author :
AlMohammad, B.F.A. ; Bose, Bella
Author_Institution :
Dept. of Math. & Comput. Sci., Kuwait Univ., Safat, Kuwait
fDate :
10/1/1999 12:00:00 AM
Abstract :
Fault-tolerant communication algorithms for k-ary n-cubes are introduced. These include: One-to-all broadcasting, all-to-all broadcasting, one-to-all personalized communication, and all-to-all personalized communication. Each of these algorithms can tolerate up to (2n-2) node failures provided that k>(2n-2) and k>3. Extensions of these algorithms with up to 2n-1 node failures are also described. The communication complexities of the proposed algorithms are derived when wormhole or store and forward packet routing is used
Keywords :
communication complexity; fault tolerant computing; multiprocessor interconnection networks; network routing; packet switching; all-to-all broadcasting; all-to-all personalized communication; communication complexities; fault-tolerant communication algorithms; k-ary n-cubes; one-to-all broadcasting; one-to-all personalized communication; store and forward packet routing; toroidal networks; wormhole; Broadcasting; Complexity theory; Computer networks; Distributed computing; Fault tolerance; Hypercubes; Intelligent networks; Multiprocessor interconnection networks; Routing; Wire;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
