A low-cost fault-tolerant structure for the hypercube

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and "almost fully" tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations-expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired-the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.

Original languageEnglish
Pages (from-to)203-216
Number of pages14
JournalJournal of Supercomputing
Volume20
Issue number3
DOIs
StatePublished - 1 Nov 2001

Keywords

  • Diagnosability
  • Fault tolerance
  • Hypercubes
  • Interconnection networks
  • Redundant systems

Fingerprint Dive into the research topics of 'A low-cost fault-tolerant structure for the hypercube'. Together they form a unique fingerprint.

Cite this