Fault-tolerant communication algorithms in toroidal networks

Non-redundant fault-tolerant communication algorithms for faulty 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. The communication complexities of the proposed algorithms are derived when cut-through or store-and-forward packet routing is used. The proposed algorithms are close to optimal in terms of communication time.