Diagnosis of ${t / {(t + 1)}}$-Diagnosable Systems
Anindya Das, K. Thulasiraman, V.K. Agarwal · SIAM Journal on Computing · 1994
A classic PMC (Preparata, Metze, and Chien) multiprocessor system [F. P Preparata, G. Metze, and R. T. Chien, IEEE Trans. Electr. Comput., EC-16 (1967), pp. 848–854] composed of n units is said to be ${t / {(t + 1)}}$ diagnosable [A. D. Friedman, A new measure of digital system diagnosis, in Dig. 1975 Int. Symp. Fault-Tolerant Comput., 1975, pp. 167–170] if, given a syndrome (complete collection of test results), the set of faulty units can be isolated to within a set of at most $t + 1$ units, assuming that at most t units in the system are faulty. This paper presents a methodology for determining when a unit $\upsilon $ can belong to an allowable fault set of cardinality at most t. Based on this methodology, for a given syndrome in a ${t / {(t + 1)}}$-diagnosable system, the authors establish a necessary and sufficient condition for a vertex v to belong to an allowable fault set of cardinality at most t and certain properties of ${t / {(t + 1)}}$-diagnosable systems. This condition leads to an ${{O(n^{3.5} )t} / {(t + 1)}}$-diagnosis algorithm. This ${t / {(t + 1)}}$-diagnosis algorithm complements the ${t / {(t + 1)}}$-diagnosability algorithm of Sullivan [The complexity of system-level fault diagnosis and diagnosability, Ph.D. thesis, Yale University, New Haven, CT, 1986].