| Author: | Mittal, Ravi; Jain, Bijendra N; Patney, Rakesh K |
| Advisor: | Advisor |
| Date: | 1994
|
| Publisher: | |
| Citation: | Microelect
|
| Series/Report no.: |
|
| Item Type: | Article
|
| Keywords: | tolerance; full binary tree; non-faulty subtree |
| Abstract: | 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. |
