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

Volume

10

Issue

10

fYear

1999

fDate

10/1/1999 12:00:00 AM

Firstpage

976

Lastpage

983

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;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.808130

Filename

808130