Fault-tolerant analysis and algorithms for a proposed augmented binary tree architecture

Abstract

An augmented binary (AB) tree architecture is proposed with a view to providing fault tolerance. This architecture is an augmentation of an n-level full binary tree with n redundant nodes and 2 n+3n-6 redundant links. The AB tree can be configured into a full binary tree even when one node is faulty at each level. While functionally equivalent to the RAE-tree, the proposed AB tree has a regular topology, reduced number of maximum input-output channels per processor, and fewer wire crossovers when implemented using very large-scale integration layout. A reconfiguration algorithm, which constructs an n-level full binary tree from an n-level faulty AB tree, is given. A distributed fault diagnosis algorithm is given which runs concurrently on each nonfaulty processor, enabling each nonfaulty processor to identify all faulty processors