Performance Modeling of Stochastic Diagnosis Engines

Critical systems are complex, consisting of thousands of components, which can fail at any time. Diagnosing these systems within a certain time is highly desirable. Traditional diagnosis algorithms are mostly deterministic, able to find single faults extremely fast and double faults reasonably quick as well. However, these algorithms fail to find diagnoses fast enough in cases where there are three or more components failing simultaneously. A stochastic algorithm, like SAFARI, is able to diagnose these problems in reasonable time. However, stochastic algorithms are unable to guarantee optimality and completeness of the returned diagnoses. In this thesis we analyze the behavior of the SAFARI algorithm, introducing a characterization of performance. We provide a performance model for this stochastic algorithm and we propose a termination criterion which guarantees a certain level of completeness of the most important set of diagnoses.Computer ScienceST/SEElectrical Engineering, Mathematics and Computer Scienc