A tree structure for local diagnosis in multiprocessor systems under the comparison model

Diagnosability is an important indicator to measure the reliability of multiprocessor systems. If we focus on the status of a particular node, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed an extended star structure to diagnose a node under the comparison model. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the extended star structure mentioned above. In this paper, we propose a new testing structure and a corresponding diagnosis algorithm to diagnose a node under the comparison model and better evaluate the local diagnosability. The local diagnosability of a node is upper bounded by its degree in the system. If the local diagnosability of each node equals to its degree in the system, then we say this system has the strong local diagnosability property. Based on the new structure, we provide two sufficient conditions for a multiprocessor system to have the strong local diagnosability property. As applications, we show that the n-dimensional star graph S_n and pancake graph P_n with faulty links have the strong local diagnosability property no matter how many edges are faulty, provided that each node connects to at least three fault-free links. Moreover, we show that S_n and P_n keep the strong local diagnosability property even if they have up to 3n−12 faulty links, assuming that each node connects to at least two fault-free links. Simulations are presented to show the performance of our tree structure.