CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc92a

[img]
Preview
PDF - Published Version
See Usage Policy.

585Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc92a

Abstract

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
http://dx.doi.org/10.1109/12.142686DOIUNSPECIFIED
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:http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc92a
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11603
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:11 Sep 2008 18:48
Last Modified:26 Dec 2012 10:17

Repository Staff Only: item control page