CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:BRUispdp91

[img]
Preview
PDF - Published Version
See Usage Policy.

670Kb

Use this Persistent URL to link to this item: http://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:
URLURL TypeDescription
http://dx.doi.org/10.1109/SPDP.1991.218267DOIUNSPECIFIED
http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=218267PublisherUNSPECIFIED
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:http://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:26 Dec 2012 10:31

Repository Staff Only: item control page