EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/2420

Title: Finding nonfaulty subtrees in faulty binary tree architectures
Authors: Mittal, Ravi
Jain, Bijendra N
Patney, Rakesh K
Keywords: tolerance
full binary tree
non-faulty subtree
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.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/2420
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
mittalfin94.pdf207.27 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback