A Local Diagnosability Measure for Multiprocessor Systems

Abstract

The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. Under the PMC model, we introduce a new measure of diagnosability, called local diagnosability, and derive some structures for determining whether a vertex of a system is locally t-diagnosable. For a hypercube, we prove that the local diagnosability of each vertex is equal to its degree under the PMC model. Then, we propose a concept for system diagnosis, called the strong local diagnosability property. A system G(V, E) is said to have a strong local diagnosability property if the local diagnosability of each vertex is equal to its degree. We show that an n-dimensional hypercube Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> has this strong property, nges3. Next, we study the local diagnosability of a faulty hypercube. We prove that Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> keeps this strong property even if it has up to n-2 faulty edges. Assuming that each vertex of a faulty hypercube Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n </sub> is incident with at least two fault-free edges, we prove Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n </sub> keeps this strong property even if it has up to 3(n-2)-1 faulty edges. Furthermore, we prove that Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> keeps this strong property no matter how many edges are faulty, provided that each vertex of a faulty hypercube Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> is incident with at least three fault-free edges. Our bounds on the number of faulty edges are all tight