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

doi:10.21629/JSEE.2018.01.22

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 LIANG^1,^2,*(), Ning ZHOU¹(), Long YUN¹()

¹ School of Computer and Electronics Information, Guangxi University, Nanning 530004, China
² 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

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(2ⁿn²).

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

Jiarong LIANG, Ning ZHOU, Long YUN. t/k-fault diagnosis algorithm of n-dimensional hypercube network based on the MM^* model[J]. Journal of Systems Engineering and Electronics, 2018, 29(1): 216-222.

Figures/Tables 4

References 25

1	PREPARATA F P, METZE G, CHIEN R T. On the connection assignment problem of diagnosable systems. IEEE Trans. on Electronic Computers, 1967, 16 (6): 848- 854.
2	SOMANI A K, PELEG O. On diagnosability of large fault sets in regular topology-based computer systems. IEEE Trans. on Computers, 1996, 45 (8892): 903.
3	LIANG J R, HUANG Y, YE L C. Diagnosabilities of exchanged hypercube networks under the pessimistic one-step diagnosis strategy. Journal of Systems Engineering and Electronics, 2015, 26 (2): 415- 420. doi: 10.1109/JSEE.2015.00048
4	YE L C, LIANG J R. Five-round adaptive diagnosis in Hamiltonian networks. IEEE Trans. on Parallel and Distributed Systems, 2015, 26 (9): 2459- 2464. doi: 10.1109/TPDS.2014.2350480
5	ZHU Q, GUO G, WANG D. Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks. IEEE Trans. on Computers, 2014, 63 (7): 881- 885.
6	HSU H C, WU K S, LIN C K, et al. A linear time pessimistic diagnosis algorithm for hyper mesh multiprocessor systems under the PMC model. IEEE Trans. on Computers, 2014, 63 (12): 2894- 2904. doi: 10.1109/TC.2013.172
7	LIN C K, KUNG T L, TAN J J M. An algorithmic approach to conditional-fault local diagnosis of regular multiprocessor interconnected systems under the PMC model. IEEE Trans. on Computers, 2013, 62 (3): 493- 451.
8	CHANG N W, HSIEH S Y. Conditional diagnosability of augmented hypercubes under the PMC model. IEEE Trans. on Dependable and Secure Computing, 2012, 9 (1): 46- 60. doi: 10.1109/TDSC.2010.59
9	TSAI C H. A quick pessimistic diagnosis algorithm for hypercube-like multiprocessor systems under the PMC model. IEEE Trans. on Computers, 2013, 62 (2): 259- 267. doi: 10.1109/TC.2011.228
10	LAI P L, TAN J J M, CHANG C P, et al. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. on Computers, 2005, 54 (2): 165- 175. doi: 10.1109/TC.2005.19
11	LIN L, ZHOU S, XU L, et al. The extra connectivity and conditional diagnosability of alternating group networking. IEEE Trans. on Parallel and Distributed Systems, 2015, 26 (3): 2352- 2362.
12	ZHOU S, XU J M. Fault diagnosability of arrangement graphs. Information Science, 2013, 24 (6): 177- 190.
13	MALEK M. A comparison connection assignment for diagnosis of multiprocessor systems. Proc. of the 7th International Symposium on Computer Architecture, 1980: 31-35.
14	MAENG J, MALEK M. A comparison connection assignment for self-diagnosis of multiprocessor systems. Proc. of the International Symposium on Fault Tolerant Computing, 1981, 30: 173-175.
15	SENGUPTA A, DANBURA A T. On self-diagnosable multiprocessor systems: diagnosis by the comparison approach. IEEE Trans. on Computers, 1992, 41 (11): 1386- 1396. doi: 10.1109/12.177309
16	YE L C, LIANG J R, LIN H X. A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model. IEEE Trans. on Computers, 2016, 65 (9): 2884- 2888. doi: 10.1109/TC.2015.2506562
17	CHEN C A, CHANG G Y, HSIEH S Y. Conditional (t, k)-diagnosis in graphs by using the comparison diagnosis model. IEEE Trans. on Computers, 2015, 64 (6): 1622- 1632.
18	YE T L, HSIEH S Y. A scalable comparison based diagnosis algorithm for hypercube-like networks. IEEE Trans. on Reliability, 2013, 62 (4): 789- 799. doi: 10.1109/TR.2013.2284743
19	YANG X, CAO J, MEGSON G M, et al. Minimum neighborhood in a generalized hypercube. Information Processing Letters, 2006, 97 (3): 88- 93. doi: 10.1016/j.ipl.2005.10.003
20	YANG X, MEGSON G M, CAO J, et al. A lower bound on the size of k-neighborhood in generalized hypercubes. Applied Mathematics and Computation, 2006, 179 (1): 47- 54.
21	SOMANI A K, AGARWAL V K, AVIS D. A generalized theory for system-level diagnosis. IEEE Trans. On Computers, 1987, 36 (5): 538- 546.
22	YANG X, EVANS D J, CHEN B, et al. On the maximal connected component of hypercube with faulty vertices. International Journal of Computer Mathematics, 2004, 81 (5): 515- 525. doi: 10.1080/00207160410001661726
23	LIANG J R, ZHANG Q. The t/s-diagnosability of hypercube networks under the PMC and comparison models. IEEE Access, 2017, 5 (1): 5340- 5346.
24	HUI Y, YANG X F, AMIY N. A (4n-9)/3 diagnosis algorithm for generalized hypercube networks. International Journal of Parallel, Emergent and Distributed Systems, 2010, 25 (3): 171- 182. doi: 10.1080/17445760903225700
25	LIN L, XU L, ZHOU S, et al. The t/k-diagnosbility for regular networks. IEEE Trans. on Computers, 2016, 65 (10): 3157- 3170. doi: 10.1109/TC.2015.2512866

Comparator	A pair of compared processors	Test outcome
Fault-free	None is faulty	0
Fault-free	One or two are faulty	1
Faulty	All situations	1 or 0

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 4

References 25

Related Articles 1

Recommended Articles

Metrics

Comments