Diagnosis of t / (t + 1)-Diagnosable Systems

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 υ 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(n3.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].