All-to-all broadcasting in faulty hypercubes

Abstract

A new fault-tolerant all-to-all broadcasting algorithm in an n-dimensional hypercube with up to [n/2] faulty links is given. An extension of this algorithm that can tolerate up to [n/2] faulty nodes is also described. These algorithms assume a multiport I/O model, meaning each node can send and receive messages from all its adjacent nodes simultaneously. The total time steps taken by the proposed algorithms are near optimal, and they produce a factor of n less traffic than previously known algorithms.