On designing and reconfiguring k-fault-tolerant tree architectures
Shantanu Dutt, John P. Hayes · IEEE Transactions on Computers · 1990
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>