Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (1): 216-222.doi: 10.21629/JSEE.2018.01.22

• Reliability • Previous Articles    

t/k-fault diagnosis algorithm of n-dimensional hypercube network based on the MM* model

Jiarong LIANG1,2,*(), Ning ZHOU1(), Long YUN1()   

  1. 1 School of Computer and Electronics Information, Guangxi University, Nanning 530004, China
    2 Guangxi Key Laboratory of Multimedia Communications and Network Technology, Nanning 530004, China
  • Received:2015-04-22 Online:2018-02-26 Published:2018-02-23
  • Contact: Jiarong LIANG E-mail:gxuliangjr@163.com;261696714@qq.com;yunlong920@163.com
  • About author:LIANG Jiarong was born in 1966. He received his B.E. degree in mathematics from Central China Normal University in 1991. He further received his M.S. degree in applied mathematics from Northwestern University in 1994 and Ph.D. degree in Institute of Automation from South China University of Technology in 1998. He is a processor and doctoral supervisor in School of Computer and Electronics Information, Guangxi University. His research interests are parallel and distributed systems, wireless sensor network, and fault diagnosis for networks. E-mail: gxuliangjr@163.com|ZHOU Ning was born in 1987. He received his B.E. degree in industrial engineering from Hefei University of Technology, China, in 2012. He is currently working towards his M.S. degree in School of Computer and Electronics Information, Guangxi University. His research interests include graph theory, network fault tolerance, and fault diagnosis for networks. E-mail: 261696714@qq.com|YUN Long was born in 1992. He received his B.E. degree in computer science and technology from Jiangsu Normal University in 2014. He is currently working towards his M.S. degree in School of Computer and Electronics Information, Guangxi University. His research interests include graph theory, parallel and distributed computing, and fault diagnosis for networks. E-mail: yunlong920@163.com
  • Supported by:
    the National Natural Science Foundation of China(61363002);This work was supported by the National Natural Science Foundation of China (61363002)

Abstract:

Compared with accurate diagnosis, the system's selfdiagnosing 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 ndimensional 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).

Key words: hypercube network, t/k-diagnosis algorithm, multiprocessor systems, the Maeng and Malek (MM)* model, Preparata, Metze, and Chien (PMC)