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