Analysis and experimental evaluation of comparison-based system-level diagnosis for multiprocessor systems

A comparison-based model for system-level fault diagnosis that generalizes both the classical PMC model and the Maeng/Malek comparison model is studied. A new necessary and sufficient condition for a system to be t-diagnosable under this model is proven. Also, a class of systems that uses the minimum number of communication links to obtain a given degree of diagnosability is presented. Next, a distributed diagnosis algorithm is presented that can reduce the number of tests necessary for diagnosis when the number of faults is relatively small. To demonstrate the practicality of our diagnosis approach, a fault table based diagnosis algorithm suitable for relatively small systems has been implemented in the Common Spaceborne Multicomputer Operating System (COSMOS). A simulator for the JPL MAX multicomputer system running COSMOS was used to test the algorithm and evaluate its performance. The results show that the algorithm diagnoses all fault situations with low latency and very little overhead.<>