Diagnosability of the lexicographic product of cycles and paths under PMC Model

By increasing the number of processors and with the help of the large-scale interconnection networks built on processors, the advanced multiprocessor systems, obtain their superpower of computing. However, the large-scale interconnection networks are very significant to the performance of any multiprocessor systems, but it also makes multiprocessor systems difficult to diagnose and isolate faulty processors. That's why the multiprocessor systems should have a better fault diagnosis ability to ensure its reliability, and the ability of fault diagnosis of a multiprocessor system is normally measured by its diagnosability. Lexicographic product is a common method to construct a large scale interconnection network, so studying the diagnosability of multiprocessor system generated by the lexicographic product of networks will be beneficial to the development of multiprocessor systems. In this paper, we use the extending stars to obtain the accurate value of the diagnosability of the interconnection networks constructed by lexicographic product of m-order paths with n-order cycles, and prove that the diagnosability of lexicographic product of network is better than the Cartesian product of networks in certain cases.