An 0(n2.5) Fault Identification Algorithm for Diagnosable Systems

Abstract

Consider a system composed of n independent processors, each of which tests a subset of the others. It is assumed that at most tp of these processors are permanently faulty and that the outcome of a test is reliable if and only if the processor which performed the test is fault free. Such a system is said to be tp-diagnosable if, given any complete collection of test results, the set of faulty processors can be uniquely identified. In this paper, it is shown that tp-diagnosable systems, due to their robust interconnection structure, possess heretofore unknown graph theoretic properties relative to vertex cover sets and maximum matchings. An 0(n2.5) algorithm is given which exploits these properties to identify the set of faulty processors in a tp-diagnosable system. The algorithm is shown to be correct, complete, not based on any conjecture, and superior to any other known fault identification algorithm for the general class of tp-diagnosable systems.