t/k-fault diagnosis algorithm of n-dimensional hypercube network based on the MM ∗ model
School of Computer and Electronics Information, Guangxi University, Nanning 530004, China, Jiarong Liang, Guangxi Key Laboratory of Multimedia Communications and Network Technology, Nanning 530004, China, Ning Zhou, School of Computer and Electronics Information, Guangxi University, Nanning 530004, China, Long YUN, School of Computer and Electronics Information, Guangxi University, Nanning 530004, China · Journal of Systems Engineering and Electronics · 2018
Compared with accurate diagnosis, the system's self-diagnosing capability can be greatly increased through the t/k-diagnosis strategy at most k vertexes to be mistakenly identified as faulty under the comparison model, where k is typically a small number. Based on the Preparata, Metze, and Chien (PMC) model, the n-dimensional hypercube network is proved to be t/k-diagnosable. In this paper, based on the Maeng and Malek (MM)* model, a novel t/k-fault diagnosis (1 ≤ k ≤ 4) algorithm of n-dimensional hypercube, called t/k-MM*-DIAG, is proposed to isolate all faulty processors within the set of nodes, among which the number of fault-free nodes identified wrongly as faulty is at most k. The time complexity in our algorithm is only O(2nn2).