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. doi:10.1109/12.142686. https://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc92a
![]()
|
PDF
- Published Version
See Usage Policy. 599kB |
Use this Persistent URL to link to this item: https://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: |
| ||||||
ORCID: |
| ||||||
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 | ||||||
Issue or Number: | 5 | ||||||
DOI: | 10.1109/12.142686 | ||||||
Record Number: | CaltechAUTHORS:BRUieeetc92a | ||||||
Persistent URL: | https://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: | INVALID USER | ||||||
Deposited On: | 11 Sep 2008 18:48 | ||||||
Last Modified: | 08 Nov 2021 22:01 |
Repository Staff Only: item control page