Fault tolerant broadcasting in SIMD hypercubes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
Editors Anon
PublisherPubl by IEEE
Pages348-351
Number of pages4
ISBN (Print)081864222X
Publication statusPublished - 1993 Dec 1
EventProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing - Dallas, TX, USA
Duration: 1993 Dec 11993 Dec 4

Publication series

NameProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing

Other

OtherProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
CityDallas, TX, USA
Period93-12-0193-12-04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Fault tolerant broadcasting in SIMD hypercubes'. Together they form a unique fingerprint.

Cite this