A Tree Structure for Local Diagnosis in Multiprocessor Systems Under Comparison Model

If we only care about the status of a particular vertex, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed an extended star structure to diagnose a vertex under 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 corresponding diagnosis algorithm to diagnose a vertex under comparison model to better evaluate the local diagnosability. The local diagnosability of a vertex is upper bounded by its degree in the system. If the local diagnosability of each vertex equals to its degree in the system then we say this system has the strong local diagnosability property. Based on the new structure, we show that the n-dimensional star graph S_n with faulty links has the strong local diagnosability property provided that each vertex connects to at least three fault-free links. Simulations are presented to show the performance of our tree structure.