A Caltech Library Service

Fault-tolerant meshes with minimal numbers of spares

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.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
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
Record Number:CaltechAUTHORS:BRUispdp91
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12402
Deposited On:24 Nov 2008 23:09
Last Modified:08 Nov 2021 22:28

Repository Staff Only: item control page