Undirected graph models for system-level fault diagnosis

The author considers two comparison-based diagnosis models previously introduced by K.Y. Chwa et al. (1981) and M. Malek (1980). For each of them, classical t-diagnosability and probabilistic diagnosability based on the maximum likelihood principle are discussed, probabilistic model for comparison testing is introduced. In all considered models, optimal diagnosable systems, i.e., those which use the least possible number of testing links, are designed. These systems have a linear number of links and can be diagnosed in linear time. It is proved, however, that for general systems, both diagnosis and diagnosability problems are NP-hard. The model is used for fault diagnosis of multiprocessor systems