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
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc92a
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.
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Kristin Buxton|
|Deposited On:||11 Sep 2008 18:48|
|Last Modified:||26 Dec 2012 10:17|
Repository Staff Only: item control page