IEEE Transactions on Computers · 1990 · 52 citations · 10 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureFault ToleranceInterconnection NetworksFault ModelingFault Tolerance DesignHardware Fault ToleranceReliable System DesignCovering DesignsFault Tolerance In MultiprocessorsFault Tolerant ArchitecturesFault-tolerant Interconnection NetworksFault-tolerant Reconfigurable SystemsInterconnection Network SynthesisReconfigurable Fault-tolerant ArchitectureTree Covering
A general approach to designing tree structured multiprocessors with optimal or near-optimal fault tolerance properties is developed. A multiprocessor architecture with a static interconnection network is represented by a graph whose nodes are processors and whose edges are interprocessor communication links. The design of k-fault-tolerant (FT) trees for arbitrary k is considered, with the primary goal of minimizing the number of spare nodes and edges. Also presented are strategies for reconfiguring a k-FT supergraph of a tree T around faults to obtain a fault-free tree isomorphic to T. A systematic methodology is presented for designing k-FT nonhomogeneous symmetry d-ary trees based on a concept termed node covering. The designs are shown to be optimal when k<d and near-optimal otherwise. It is also shown that these k-FT designs can be implemented efficiently using switches to share redundant links.<<ETX>>
10
A Graph Model for Fault-Tolerant Computing Systems
Hayes · IEEE Transactions on Computers · 1976 · 215 citations
Alvin M. Despain, David A. Patterson · 1978 · 163 citations