Local Diagnosability under the PMC Diagnosis Model with Application to Star Graphs

Abstract

In this paper, we introduce a new measure of diagnosability, called local diagnosability, and provide a substructure for determining if a node is locally t-diagnosable under the PMC model. We prove that the local diagnosability of the star graph at each node is equal to its degree. Then, we propose a concept called strong local diagnosability property. We show that an n-dimensional star graph Sn has this strong property, n³3. Next, we prove that Sn keeps this strong property even if it has up to n-3 faulty edges. Besides, we propose a new diagnosis algorithm for general systems. The time complexity of our algorithm to diagnose all the faulty processors is bounded by O(N logN), where N is the total number of processors.