[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Intermittent Fault Diagnosability of Interconnection Networks

  • Regular Paper
  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

Abstract

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 cn in -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 t i -fault diagnosable system without repair if and only if its minimum in-degree is greater than t i under the BGM (Barsi, Grandoni, and Masetrini) model. Finally, we extend the necessary and sufficient conditions to determine whether an interconnection network S is t i -fault diagnosable without repair under the MM (Maeng and Malek) model from the permanent fault situation to the intermittent fault situation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

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

    Article  MathSciNet  MATH  Google Scholar 

  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.

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  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.

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  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.

    Article  MathSciNet  Google Scholar 

  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.

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

  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.

    MATH  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

  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.

    Article  Google Scholar 

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

    MathSciNet  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  34. Dally W. Performance analysis of k-ary n-cube interconnection networks. IEEE Transactions on Computers, 1990, 39(6): 775-785.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer and Electronic Information, Guangxi University, Nanning, 530004, China

    Jia-Rong Liang & Hao Feng

  2. Department of Computer and Information Sciences, Temple University, Philadelphia, PA, 19122, U.S.A.

    Xiaojiang Du

Authors
  1. Jia-Rong Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hao Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaojiang Du
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jia-Rong Liang.

Electronic supplementary material

Below is the link to the electronic supplementary material.

ESM 1

(PDF 135 kb)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liang, JR., Feng, H. & Du, X. Intermittent Fault Diagnosability of Interconnection Networks. J. Comput. Sci. Technol. 32, 1279–1287 (2017). https://doi.org/10.1007/s11390-017-1800-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11390-017-1800-5

Keywords