The ( t, k )-diagnosability of shuffle-cubes under PMC model
Jin'e Li, Limei Lin, Yanze Huang, Hui Yong Yu, Riqing Chen · International Journal of Computer Mathematics Computer Systems Theory · 2019
System-level diagnosis aims to identify faulty processors in a multiprocessor system by analysing the test results among the processors. The (t,k)-diagnosis requires to identify and repair at least k faulty processors in each iteration until that all t faulty processors are found where t≥k. It is one of the most important system-level diagnosis strategies. Meanwhile, shuffle-cube SQn, a variant of hypercube for multiprocessor systems, has some good combinatorial properties and fault-tolerant properties. In this paper, we propose a (t,k)-diagnosis algorithm for n-dimensional shuffle-cube SQn, and then we show that SQn is (t,k)-diagnosable. Moreover, we prove that the proposed algorithm can identify at most 2n9 faulty nodes under the condition that it can identify at least n faulty nodes in each iteration.