›› 2017, Vol. 32 ›› Issue (6): 1279-1287.doi: 10.1007/s11390-017-1800-5

Special Issue: Computer Networks and Distributed Computing

• Regular Paper • Previous Articles     Next Articles

Intermittent Fault Diagnosability of Interconnection Networks

Jia-Rong Liang1, Hao Feng1, Xiaojiang Du2, Senior Member, IEEE   

  1. 1 School of Computer and Electronic Information, Guangxi University, Nanning 530004, China;
    2 Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, U.S.A
  • Received:2016-09-15 Revised:2017-03-10 Online:2017-11-05 Published:2017-11-05
  • Contact: 10.1007/s11390-017-1800-5
  • About author:Jia-Rong Liang received his B.E.degree in mathematics from Central China Normal University,Wuhan,in 1991,his M.S.degree in applied mathematics from Northwest University,Xi'an,in 1995,and his Ph.D.degree in automatic control from South China University of Technology,Guangzhou,in 1998.He is currently a professor in School of Computer and Electronic Information,Guangxi University,Nanning.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61363002, and the Natural Science Foundation of Guangxi Zhuang Autonomous Region of China under Grant No. 2016GXNSFAA380134.

An interconnection network's diagnosability is an important metric for measuring its self-diagnostic capability. Permanent fault and intermittent fault are two different fault models that exist in an interconnection network. In this paper, we focus on the problem pertaining to the diagnosability of interconnection networks in an intermittent fault situation. First, we study a class of interconnection networks called crisp three-cycle networks, in which the cnin-number (the number of common vertices each pair of vertices share) is no more than one. Necessary and sufficient conditions are derived for the diagnosability of crisp three-cycle networks under the PMC (Preparata, Metze, and Chien) model. A simple check can show that many well-known interconnection networks are crisp three-cycle networks. Second, we prove that an interconnection network S is a ti-fault diagnosable system without repair if and only if its minimum in-degree is greater than ti under the BGM (Barsi, Grandoni, and Masetrini) model. Finally, we extend the necessary and sufficient conditions to determine whether an interconnection network S is ti-fault diagnosable without repair under the MM (Maeng and Malek) model from the permanent fault situation to the intermittent fault situation.

[1] Mallela S, Masson G M. Diagnosable systems for intermittent faults. IEEE Transactions on Computers, 1978, 27(6):560-566.

[2] Hong W, Hsien S. Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model. IEEE Transactions on Reliability, 2012, 62(1):140-148.

[3] Preparata F, Metze G, Chien R. On the connection assignment problem of diagnosable system. IEEE Transactions on Computers, 1967, 16(6):848-854.

[4] Peng S, Lin C, Tan J et al. The g-good-neighbor conditional diagnosability of hypercube under PMC model. Applied Mathmatics and Computation, 2012, 218(21):10406-10412.

[5] Ye L, Liang J. Five-round adaptive diagnosis in Hamiltonian networks. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(9):2459-2464.

[6] Araki T, Shibata Y. (t, k)-fault diagnosable system:A generalization of the PMC models. IEEE Transactions on Computers, 2003, 52(7):971-975.

[7] Somani A, Agarwal V, Avis D. A generalized theory for system level diagnosis. IEEE Transactions on Computers, 1987, 36(5):538-546.

[8] Chang G, Chang G, Chen G. Diagnosability of regular networks. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(4):314-323.

[9] Kavianpour A, Kim K. Diagnosability of hypercubes under the pessimistic one-step strategy. IEEE Transactions on Computers, 1991, 40(2):232-237.

[10] Chang N, Hsieh S. Structural properties and conditional diagnosability of star graphs by using the PMC model. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(11):3002-3011.

[11] Lin L, Zhou S, Xu L, Wang D. The extra connectivity and conditional diagnosability of alternating group networks. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(8):2352-2362.

[12] Lin L, Xu L, Zhou S, Hsieh S. The t/k-diagnosability for regular networks. IEEE Transactions on Computers, 2016, 65(10):3157-3170.

[13] Barsi F, Grandoni F, Masetrini P. A theory of diagnosability of digital systems. IEEE Transactions on Computers, 1976, 25(6):585-593.

[14] Albini L, Chessa S, Maestrini P. Diagnosis of symmetric graphs under the BGM model. Computer Journal, 2004, 47(1):85-92.

[15] Maeng J, Malek M. A comparison connection assignment for self-diagnosis of multiprocessor systems. In Proc. the 11th International Symposium of Fault-Tolerant Computing, March 1981, pp.173-175.

[16] Sengupta A, Dahbura A. On self-diagnosable multiprocessor systems:Diagnosis by the comparison approach. IEEE Transactions on Computers, 1992, 41(11):1386-1396.

[17] Hsieh S, Lee C. Diagnosability of two-match composition networks under the MM* model. IEEE Transactions on Dependable and Scure Computing, 2011, 8(2):246-255.

[18] Ye T, Hsieh S. A scalable comparison-based diagnosis algorithm for hypercube-like networks. IEEE Transactions on Reliability, 2013, 62(4):789-799.

[19] Wang D. Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model. IEEE Transactions on Computers, 1999, 48(12):1369-1374.

[20] Hsieh S, Chen Y. Strongly diagnosable product networks under comparison diagnosis model. IEEE Transactions on Computers, 2008, 57(6):721-732.

[21] Zhu Q, Guo G, Wang D. Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks. IEEE Transactions on Computers, 2014, 63(7):1847-1851.

[22] Ye L, Liang J, Lin H. A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model. IEEE Transactions on Computers, 2016, 65(9):2884-2888.

[23] Dahbura A, Masson G M. An O(n2.5) fault identification algorithm for diagnosable systems. IEEE Transactions on Computers, 1990, 33(6):486-492.

[24] Chang N, Deng W, Hsieh S. Conditional diagnosability of (n, k)-star networks under the comparison diagnosis model. IEEE Transactions on Reliability, 2015, 64(1):132-143.

[25] Hsieh S, Kao C. The conditional diagnosability of k-ary ncubes under the comparison diagnosis model. IEEE Transactions on Computers, 2013, 62(4):839-843.

[26] Xu L, Lin L, Zhou S, Hsieh S. The extra connectivity, extra conditional diagnosability, and t/m-diagnosability of arrangement graphs. IEEE Transactions on Reliability, 2016, 65(3):1248-1262.

[27] Lin L, Zhou S, Xu L, Wang D. The extra connectivity and conditional diagnosability of alternating group networks. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(8):2352-2362.

[28] Chen C, Hsieh S. Component-composition graphs:(t, k)-diagnosability and its application. IEEE Transactions on Computers, 2013, 62(6):1097-1110.

[29] Hsieh S, Tsai C, Chen C. Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes. IEEE Transactions on Computers, 2013, 62(7):1472-1477.

[30] Liang J, Huang Y, Ye L. Diagnosabilities of exchanged hypercube networks under the pessimistic one-step diagnosis strategy. Journal of Systems Engineering and Electronics, 2015, 26(2):415-420.

[31] Fan J, He L. BC connection networks and their properties. Chinese Journal of Computers, 2003, 26(1):84-90. (in Chinese)

[32] Chiang W, Chen R. Topological properties of the (n, k)-star graph. International Journal of Foundations of Computer Science, 1998, 9(2):235-248.

[33] Loh P, Hsu W, Pan Y. The exchanged hypercube. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9):866-874.

[34] Dally W. Performance analysis of k-ary n-cube interconnection networks. IEEE Transactions on Computers, 1990, 39(6):775-785.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved