Diagnosability for a family of matching composition networks

We study here the diagnosability of networks under two models of self-diagnosis: PMC model introduced by Preparata, Metze and Chien (IEEE Trans Electronic Computers 16(12):848-854 (1967)) and MM* model introduced by Sengupta and Dahbura (IEEE Trans Computers 41(11):1386-1396 (1992)) which is the variant of the comparison model (1980). The diagnosability of a network of processors is the maximum number of faulty processors that can be identified by the network itself. Lee and Hsieh (IEEE Trans Dependable Secure Comput 8(2):246-255 (2011)) considered the diagnosability of networks obtained by connecting two networks of the same order by two perfect matchings and got the lower bounds. Usually, there is a gap between the lower bound and the exact value of the diagnosability. In this paper, we completely determine the diagnosability of this family of matching composition networks.

Automated summary

This paper investigates the diagnosability of networks under two models of self-diagnosis and completely determines the diagnosability of a certain family of matching composition networks.