The Non-inclusion Diagnosability of Hypercubes Under the PMC Model

Diagnosability of a multiprocessor system is an important measure of the reliability of interconnection networks. System-level diagnosis is a primary strategy to identify the faulty processors in a multiprocessor system. Based on a sound assumption proposed by Zhu et al. recently, we proposed a new diagnosability named non-inclusion diagnosability and showed that the non-inclusion diagnosability t(N)(Q(n)) of the hypercube under the PMC model is 2n - 2. That is, assume that if two vertex sets F-1 and F-2 are both consistent with a syndrome and F-1 subset of F-2, then F-2 is not the faulty set which we are looking for; the faulty set F is 1-step diagnosable if vertical bar F vertical bar <= 2n - 2 in Q(n) under the PMC model.

Automated summary

This paper discusses the diagnosability of a multiprocessor system and system-level diagnosis strategy. Based on a sound assumption, a new diagnosability called non-inclusion diagnosability is proposed and its value is proven under a specific model. By limiting the size of the faulty set, one-step diagnosis can be achieved.