A new structure for a vertex to be locally t-diagnosable in large multiprocessor systems

PMC model is the test-based diagnosis which a vertex performs the diagnosis by testing the neighbor vertices via the edges between them. 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 two structures to diagnose a vertex. The local diagnosability of a vertex is upper bounded by its degree in the system. If the local diagnosability of a vertex is equal to its degree then we say it is locally optimal diagnosable. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the two structures mentioned above. Herein, we propose a new testing structure and corresponding diagnosis algorithm to diagnose a vertex under PMC model to better evaluate the local diagnosability. And this diagnosis algorithm takes linear time. Based on this new structure, we give a sufficient condition for a vertex to be locally optimal diagnosable. As its applications, we consider the sufficient and necessary condition for a vertex of hypercubes (resp. folded hypercubes) with faulty edges to be locally optimal diagnosable.(c) 2022 Elsevier B.V. All rights reserved.