Fault tolerant broadcasting in SIMD hypercubes

In this paper, we propose an optimal fault tolerant broadcasting algorithm which requires only n+1 steps for an SIMD hypercube with up to n-1 faulty nodes. The basic idea of the proposed algorithm is first to find a fault-free subcube (C_S) which contains the source node (S) such that each neighboring subcube of the subcube C_S contains at least one fault. Next, the message is broadcast along the internal dimensions followed by external dimensions of the subcube C_S. This process requires n steps. Since this process does not guarantee that all the fault-free nodes receive the message, an extra step may be needed. We prove that there exists an internal dimension of the subcube C_S such that all the nodes which did not receive the message in n steps will receive the message by broadcasting the message along that dimension. We also develop a generalized broadcasting algorithm which tolerates any number of faults.