The (t, k)-diagnosability of shuffle-cubes under PMC model. Issue 2 (3rd April 2019)

• Record Type: Journal Article
• Authors: Li, Jin'e; Lin, Limei; Huang, Yanze; Yu, Hui; Chen, Riqing
• Is Part Of: International journal of computer mathematics. Volume 4:Issue 2(2019)
• Page Start: 111
• Page End: 126
• Publication Date: 2019-04-03
• Subjects: (tk)-Diagnosability -- aggregate -- reliability -- fault diagnosis -- shuffle-cube; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2019.1625949
• Languages: English
• ISSNs: 2379-9927

Abstract

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.