Efficient Broadcasting Algorithms in Faulty Hypercubes

Abstract

In this paper, we consider fault-tolerant broadcasting in MIMD hypercubes in which each node can send message to all its neighbors simultaneously, however, each node can receive message from only one of its neighbors at each time step. Let Hn denote the n-dimensional hypercube. Hn is called d-safe if each node of Hn has at least d fault-free neighbors. We give efficient broadcasting algorithms for d-safe (d≧1) Hn with up to 2d(n-d)-1 faulty nodes. For the case of d=1, our algorithm completes the broadcasting in optimal time steps. For d＞1, we show an algorithm which completes the broadcasting in n+O (d2) time step. All the algorithms have optimal traffic steps.