A Caltech Library Service

Tolerating faults in hypercubes using subcube partitioning

Bruck, Jehoshua and Cypher, Robert and Soroker, Danny (1992) Tolerating faults in hypercubes using subcube partitioning. IEEE Transactions on Computers, 41 (5). pp. 599-605. ISSN 0018-9340.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We examine the issue of running algorithms on a hypercube which has both node and edge faults, and we assume a worst case distribution of the faults. We prove that for any constant c, an n-dimensional hypercube (n-cube) with n^c faulty components contains a fault-free subgraph that can implement a large class of hypercube algorithms with only a constant factor slowdown. In addition, our approach yields practical implementations for small numbers of faults. For example, we show that any regular algorithm can be implemented on an n-cube that has at most n-1 faults with slowdowns of at most 2 for computation and at most 4 for communication. To the best of our knowledge this is the first result showing that an n-cube can tolerate more than O(n) arbitrarily placed faults with a constant factor slowdown.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 1992 IEEE. Reprinted with permission. Manuscript received June 24, 1991; revised December 4, 1991.
Subject Keywords:parallel computing; reconfiguation; subcubes; computational complexity; fault tolerant computing; graph theory; hypercube networks; parallel algorithms; edge faults; fault tolerance; fault-tree subgraph; faulty components; hypercube algorithms; node faults; subcube partitioning; worst-case distribution
Record Number:CaltechAUTHORS:BRUieeetc92a
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11603
Deposited By: Kristin Buxton
Deposited On:11 Sep 2008 18:48
Last Modified:26 Dec 2012 10:17

Repository Staff Only: item control page