Finding nonfaulty subtrees in faulty binary tree architectures

In this paper we have studied fault tolerance of a full binary tree in terms of availability of non-faulty (full) subtrees. When an unaugmented full binary tree is faulty, then the computation can be carried out on the largest available non-faulty (full) binary subtree. It is shown that the minimum number of faulty nodes required to destroy all subtrees of height h in a full binary tree of height n is given as fbt(n, h) = ⌊ (2n-1) (2h-1)⌋. It follows that the availability of a non-faulty subtree of height h = n-w, in an n level full binary tree containing u faulty nodes, can be ensured, where w is the smallest integer such that u ≤ 2w. An algorithm which evaluates whether a given set of faulty nodes will destroy all subtrees of some specified height, is given. This algorithm can also evaluate the largest available non-faulty subtree in a faulty full binary tree. We also study the availability of a non-faulty subtree in some augmented binary tree architectures. © 1994.