Diagnosis of parallel computers with arbitrary connectivity
Recently, Fussell and Rangarajan [7], [12], [13] considered performing multiple tests to achieve correct diagnosis of constant degree connection structures. They showed that the probability of correctly identifying every processor approaches one as n-->infinity, where n is the number of processors in the system. In this paper, we give the performance analysis for the probabilistic diagnosis algorithm defined in [7], [12], [13]. In comparison with Ill, [12], [13], we first derive a different and formal proof for the analytic expression of the probability of the event that a fault-free processor is correctly identified. We then show an exact analytic expression for the probability of the event that a faulty processor is correctly identified. Our result improves the previous results in [7], [12], [13]. In [7], an expression for the probability of the event that a faulty processor is wrongly identified was incorrectly used, while in [12], [13] the same expression was considered as an upper bound on the probability (see our Remark 3.1). However, no reasonable justification was given or proven. Based on our new results, we finally give the asymptotic analysis for the algorithm. We demonstrate that the probability of correctly identifying every processor approaches one as n-->infinity.
performance analysis system-level diagnosis fault identification multiprocessor systems