The (t, k)-diagnosability of shuffle-cubes under PMC model

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\ge 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^{\frac{n}{9}}$ faulty nodes under the condition that it can identify at least n faulty nodes in each iteration.

KEYWORDS:

• $(tk)$-Diagnosability
• aggregate
• reliability
• fault diagnosis
• shuffle-cube

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant numbers 61702100, 61702103, 61771140], the China Postdoctoral Science Foundation [grant numbers 2018T110636, 2017M612107], and the Foundation of Digital Fujian Institute of Big Data for Agriculture and Forestry [grant number 117-KJG18019A], Fujian University of Technology [grant number GY-Z17008] and Education Department of Fujian Province [grant number JAT170397].