TY - GEN

T1 - Fault tolerant broadcasting in SIMD hypercubes

AU - Chang, Yeim-Kuan

PY - 1993/12/1

Y1 - 1993/12/1

N2 - 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 (CS) which contains the source node (S) such that each neighboring subcube of the subcube CS contains at least one fault. Next, the message is broadcast along the internal dimensions followed by external dimensions of the subcube CS. 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 CS 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.

AB - 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 (CS) which contains the source node (S) such that each neighboring subcube of the subcube CS contains at least one fault. Next, the message is broadcast along the internal dimensions followed by external dimensions of the subcube CS. 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 CS 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.

UR - http://www.scopus.com/inward/record.url?scp=0027848226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027848226&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027848226

SN - 081864222X

T3 - Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

SP - 348

EP - 351

BT - Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

Y2 - 1 December 1993 through 4 December 1993

ER -