Operative diagnosis of graph-based systems with multiple faults

The problem of multiple faults diagnosis in safety-critical systems is cons idered. Error propagation between system components is modeled as a directe d graph, where the errors propagate instantaneously along the edges. Some o f the system components are equipped with alarms, which ring when abnormal conditions are detected. A diagnosis algorithm identifies the set of potent ial failure sources based on the set of ringing alarms. This paper introduc es the D-FAULTS algorithm, which diagnoses the system when at most two node s can be failure sources at any time. The concept of sequential diagnosis i s also introduced, to deal with an unknown number of faults. Sequential dia gnosis is aimed at locating the smallest set of nodes containing at least o ne fault. Using this approach, a faulty system can be restored to normal co ndition by executing repeatedly the diagnosis and repair phases. To this pu rpose, we introduce the sequential diagnosis algorithm S-DIAG with optimal time complexity,