A Characterization of t/s-Diagnosability and Sequential t-Diagnosability in Designs
Abstract
A multiprocessing system is t/s-diagnosable if all faulty processors can be identified to within s processors provided there are no more than t faulty processors. A characterization theorem of Karunanithi and Friedman [4] for t/s-diagnosability in certain special cases of systems called designs is extended to the entire class of D(sub 1), t'(n) designs. We show that for large t , s is approximately t2/4t'. Furthermore, the minimum number of processors needed to attain a given diagnosability is derived. A multiprocessor system is sequentially t-diagnosable if at least one faulty processor can be identified provided there are no more than t faulty processors. A theorem by Preparata, Metze, and Chien [7] giving a sufficient condition for sequential t-diagnosability in the single loop system, a special case of designs, is extended to the entire class of D(sub 1), t'(n) designs. We show that, for large t, approximately t2/4t' nodes are needed for a D(sub 1), t'(n) design to be sequentially t-diagnosable.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1990
- Accession Number
- ADA593565
Entities
People
- Jon T. Butler
- Joo-kang Lee
Organizations
- Naval Postgraduate School