I t-Tole rant Com m un ication Algorithms in Toroidal Networks
Bella Bose · 1999
Fault-tolerant communication algorithms for I-ary wcubes 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 lo (21~ -. Zj node failures provided that h > (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. Index Terms-Interconnection networks, torus, k-ary wcubes, fault-free communication algorithms, fault-tolerant communication algorithms. + ~~ B.F.A. AiUdiiiwi is with tiie Dcpmlnienf of Mnlheniatics mid Computer Scieiice, Kuronit Llnivcrsity, P.O. Box 5969 Snfnl, 13000, Kiinmit. E-moii: ~~~~~~lit!,,,~f .i,~t, e B. Rose is with the Ueportmmf of Conrpuler Scietza: Orcgm Stale University, Cornnilis, OR, 97331. E-mail: bosc~~s.:s.orsl.cdii.