An algorithm for conditional-fault local diagnosis of multiprocessor systems under the MM^⁎ model

Diagnosis is a crucial subject for maintaining the reliability of multiprocessor systems. Under the MM^⁎ diagnosis model, Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N⁵) to diagnose a system with N processors. In this paper, we propose a (α,β)-trees combination S(u,X,α,β) and give an algorithm to identify the fault or fault-free status of each processor for conditional local diagnosis under the MM^⁎ model. According to our results, a connected network with a (α,β)-trees combination S(u,X,α,β) for a node u is conditionally locally (α+2β−3)-diagnosable at node u and the time complexity of our algorithm to diagnose u is O(α²β+αβ²). As an application, we show that our algorithm can identify the status of each node of n-dimensional star graph S_n if the faulty node number does not exceed 3n−8. Compared with existing algorithms, our algorithm allows more faulty nodes in a multiprocessor system.