DSpace
 

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

Full metadata record

DC FieldValueLanguage
dc.contributor.authorMittal, Ravi-
dc.contributor.authorJain, Bijendra N-
dc.contributor.authorPatney, Rakesh K-
dc.date.accessioned2007-01-12T09:37:13Z-
dc.date.available2007-01-12T09:37:13Z-
dc.date.issued1994-
dc.identifier.citationMicroelectronics and Reliability, 34(8), 1301-1310p.en
dc.identifier.urihttp://eprint.iitd.ac.in/dspace/handle/2074/2420-
dc.description.abstractIn 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.en
dc.format.extent212240 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoenen
dc.subjecttoleranceen
dc.subjectfull binary treeen
dc.subjectnon-faulty subtreeen
dc.titleFinding nonfaulty subtrees in faulty binary tree architecturesen
dc.typeArticleen
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