On t-diagnosable systems and their implications in fault tolerant computing
Kyung‐Yong Chwa · 1980
This dissertation considers (one-step) diagnosable systems with three different types of diagnosability criteria, t(,0)-diagnosability, t(,1)/t(,1)-diagnosability and t(,i)-intermittent fault diagnosability. Necessary and sufficient conditions for a t(,1)/t(,1)-diagnosable system are obtained, and a new characterization theorem for an intermittent fault diagnosable system is given. Then a class of t(,0)-diagnosable systems, denoted by D(n,t(,0),X), is considered. In this class it is shown that: (1) necessary and sufficient conditions for t(,1)/t(,1)-diagnosability are greatly simplified, (2) any system is (t(,0)-1)-intermittent fault diagnosable which is known to be the best possible for t(,0)-diagnosable systems, (3) optimal diagnosis algorithms of time complexity O(nt(,0)) exist, and most importantly, (4) given the test results, any set F of faults with (VBAR)F(VBAR) (LESSTHEQ) t(,1) can be identified to within a set F' with F (L-HOOK EQ) F' and (VBAR)F'(VBAR) (LESSTHEQ) min {t(,1), (VBAR)F(VBAR) + 1}. We also attempt to apply information theoretic concepts to fault diagnosis: Assuming systems of a priori equal computational capability made of equally unreliable units, a comparison between two basic classes of computing systems (the modular redundant systems and the t-diagnosable systems) is made based on their computational throughput and their reliability. We present an undirected graph model and propose a possible approach to diagnostic tests which may take advantage of this new model. An optimal diagnosis algorithm for this model is also presented.