COMPLEXITY OF FAULT-DIAGNOSIS IN COMPARISON MODELS

In this paper, we consider a comparison-based probabilistic model for multiprocessor fault diagnosis. We study the problem of optimal diagnosis, which is to correctly identify the status (faulty/fault-free) of units in the system, with maximum probability. For some parameter values, this probabilistic model is well approximated by the asymmetric comparison model introduced by Malek. For arbitrary systems it is shown that optimal diagnosis in the probabilistic model and in Malek's model is NP-hard. However, we construct efficient diagnosis algorithms in the asymmetric comparison model for a class of systems corresponding to bipartite graphs which includes hypercubes, grids, and forests. Furthermore, for ring systems, we present a linear-time algorithm to perform optimal diagnosis in the probabilistic model.