Design and Reconfiguration Strategies for Near-Optimal k-fault-tolerant Tree Architectures
Shantanu Dutt, John P. Hayes · 2005
A graph G(k,T) representing a multiprocessor architecture is a k-fault-tolerant (k-FT) implementation of a basic tree T, if G(k,T) contains T after removal of any k nodes. The authors consider the design of such k-FT architectures with the primary goals of minimizing the number of spare nodes and edges. The authors present a systematic methodology for designing k-FT implementations of nonhomogeneous symmetric d-ary trees based on graph covering. The resulting designs are optimal in a well-defined sense when k >