The (t, k)-diagnosability of shuffle-cubes under PMC model. Issue 2 (3rd April 2019) - Li, Jin'e; Lin, Limei; Huang, Yanze; Yu, Hui; Chen, Riqing
ABSTRACT: 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 S Q n, 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 S Q n, and then we show that S Q n is ( t, k ) -diagnosable. Moreover, we prove that the proposed algorithm can identify at most 2 n 9 faulty nodes under the condition that it can identify at least n faulty nodes in each iteration.