Authors: Brigitte Servatius , W. Shi

Reference: J. Comput. Sci. Tech. 6 (1991), no. 3, 230--242.

Abstract: A fault diagnosis model for multiprocessor computers is proposed. Under normal operating mode each processor executes its own data. When an error occurs, the system is switched to the diagnostic mode. Previous input data for each processor is shifted to a diŽerent unit, to obtain a set of comparison results. We show that analysis of the test data to diagnose or locate faulty processors is equivalent to a 2-satis¯ability problem. Under the assumption that discrepancy in a comparison result occurs if and only if at least one of the processors (being compared) is faulty, we prove that all the faulty processors can be diagnosed in O(n^2) time, where n denotes the number of processors in the system.