A Study Of Pessimistic Diagnosis Algorithm Under The MM*Model

Multicomputer systems provide a powerful platform for high-performancecomputing and high-capacity distributed data storage. The extensive utilization ofmulticomputer systems has become an important indication to reflect the level of acountry’s economic development and information-based construction. With the growingsizes of multicomputers, the probability of existence of failing nodes in a system alsoincreases. Therefore, how to maintain high system reliability and availability hasbecome an urgent problem. A major means to improve system reliability is the timelydiagnosis of failing nodes, followed by replacement or repair. System-level diagnosisprovides an effective approach to the fault diagnosis of multicomputers.Compared totp-diagnosability system,t₁/t₁-diagnosability can significantlyimprove a system’s self-diagnostic capability at the cost of at most one normal nodepossibly being diagnosed as “faulty”. Therefore, the study oft₁/t₁-diagnosable systemis of practical importance. This thesis addresses the fault diagnosis oft₁/t₁-diagnosablesystems under MM*model. The main contributions of this thesis are listed below:Some properties oft₁/t₁-diagnosable systems are explored. On this basis, weproposed a fault diagnosis algorithm oft₁/t₁-diagnosable systems under the MM*model, which runs inO（n2.5）time, where n denotes the total number of nodes. Theproposed algorithm can isolate a set of at mostt₁faulty units, F, to a set U, with|U|≦min{t₁,|F|+1}. From the output of the algorithm, it can be determined whether allthe nodes in U are faulty or U contains at most one fault-free node. Finally, thecorrectness of the algorithm is proved, and its time cost is analyzed. To our knowledge,this is the first time to propose a diagnosis algorithm fort₁/t₁-diagnosable systemsunder the MM*model.