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 -