Operative diagnosis of graph-based systems with multiple faults

The problem of multiple faults diagnosis in safety-critical systems is considered. Error propagation between system components is modeled as a directed graph, where the errors propagate instantaneously along the edges. Some of the system components are equipped with alarms, which ring when abnormal conditions are detected. A diagnosis algorithm identifies the set of potential failure sources based on the set of ringing alarms. This paper introduces the D-FAULTS algorithm, which diagnoses the system when at most two nodes can be failure sources at any time. The concept of equential diagnosis is also introduced, to deal with an unknown number of faults. Sequential diagnosis is aimed at locating the smallest set of nodes containing at least one fault. Using this approach, a faulty system can be restored to normal condition by executing repeatedly the diagnosis and repair phases. To this purpose, we introduce the sequential diagnosis algorithm S-DIAG with optimal time complexity