Fault-tolerant meshes with minimal numbers of spares

10 December 2002

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 288-295
https://doi.org/10.1109/spdp.1991.218267

Abstract

Presents several techniques for adding fault-tolerance to distributed memory parallel computers. More formally, given a target graph with n nodes, the authors create as 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. The authors present fault-tolerant graphs for target graphs which are 2-dimensional meshes, tori, eight-connected meshes and hexagonal meshes. In all cases these fault-tolerant graphs have smaller degree than any previously known graphs with the same properties.

Keywords

This publication has 22 references indexed in Scilit:

Asymptotically tight bounds for computing with faulty arrays of processors
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Fault-tolerant array processors using single-track switches
IEEE Transactions on Computers, 1989
Fast computation using faulty hypercubes
Published by Association for Computing Machinery (ACM) ,1989
Optimized mesh-connected networks for SIMD and MIMD architectures
Published by Association for Computing Machinery (ACM) ,1987
Efficient Spare Allocation for Reconfigurable Arrays
IEEE Design & Test of Computers, 1987
Minimumk-hamiltonian graphs, II
Journal of Graph Theory, 1986
Wafer-Scale Integration of Systolic Arrays
IEEE Transactions on Computers, 1985
The Diogenes Approach to Testable Fault-Tolerant Arrays of Processors
IEEE Transactions on Computers, 1983
A Graph Model for Fault-Tolerant Computing Systems
IEEE Transactions on Computers, 1976
Graphs with circulant adjacency matrices
Journal of Combinatorial Theory, 1970