Bruck, Jehoshua and Cypher, Robert and Ho, Ching-Tien (1991) Fault-tolerant meshes with minimal numbers of spares. In: IEEE Symposium on Parallel and Distributed Processing, 3rd, Dallas, TX, 2-5 December 1991. IEEE , Piscataway, NJ, pp. 288-295. ISBN 0-8186-2310-1. https://resolver.caltech.edu/CaltechAUTHORS:BRUispdp91
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 686kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:BRUispdp91
Abstract
This paper presents several techniques for adding fault-tolerance to distributed memory parallel computers. More formally, given a target graph with n nodes, we create a fault-tolerant graph with n + k nodes such that given any set of k or fewer faulty nodes, the remaining graph is guaranteed to contain the target graph as a fault-free subgraph. As a result, any algorithm designed for the target graph will run with no slowdown in the presence of k or fewer node faults, regardless of their distribution. We present fault-tolerant graphs for target graphs which are 2-dimensional meshes, tori, eight-connected meshes and hexagonal meshes. In all cases our fault-tolerant graphs have smaller degree than any previously known graphs with the same properties.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © Copyright 1991 IEEE. Reprinted with permission. Meeting Date: 12/02/1991 - 12/05/1991. | |||||||||
| Subject Keywords: | distributed memory systems; fault tolerant computing; parallel architectures; distributed memory; fault-tolerance; fault-tolerant graphs; fault-tolerant meshes; parallel computers; target graph | |||||||||
| DOI: | 10.1109/SPDP.1991.218267 | |||||||||
| Record Number: | CaltechAUTHORS:BRUispdp91 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:BRUispdp91 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 12402 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Kristin Buxton | |||||||||
| Deposited On: | 24 Nov 2008 23:09 | |||||||||
| Last Modified: | 08 Nov 2021 22:28 |
Repository Staff Only: item control page
