EPrints@IIT Delhi >
Faculty Research Publicatons >
Computer Science and Engineering >
Please use this identifier to cite or link to this item:
|Title: ||Finding nonfaulty subtrees in faulty binary tree architectures|
|Authors: ||Mittal, Ravi|
Jain, Bijendra N
Patney, Rakesh K
full binary tree
|Issue Date: ||1994|
|Citation: ||Microelectronics and Reliability, 34(8), 1301-1310p.|
|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.|
|Appears in Collections:||Computer Science and Engineering|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.