We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 38 Issue 4
July  2023
Turn off MathJax
Article Contents
Abstract
Conflict of Interest
References
Related Articles
Supplements
Sun XL, Fan JX, Cheng BL et al. Probabilistic fault diagnosis of clustered faults for multiprocessor systems. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 38(4): 821−833 July 2023. DOI: 10.1007/s11390-021-1099-0.
Citation: Sun XL, Fan JX, Cheng BL et al. Probabilistic fault diagnosis of clustered faults for multiprocessor systems. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 38(4): 821−833 July 2023. DOI: 10.1007/s11390-021-1099-0.
shu

Probabilistic Fault Diagnosis of Clustered Faults for Multiprocessor Systems

  • 1.

    School of Computer Science and Technology, Soochow University, Suzhou 215006, China

  • 2.

    Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou 215006, China

Funds: This work was supported by the National Natural Science Foundation of China under Grant Nos. 62172291, 62272333, and U1905211, the Postgraduate Research and Practice Innovation Program of Jiangsu Province of China under Grant No. KYCX21_2961, Jiangsu Province Department of Education Future Network Research Fund Project under Grant No. FNSRFP-2021-YB-39, the Priority Academic Program Development of Jiangsu Higher Education Institutions, and the Collaborative Innovation Center of Novel Software Technology and Industrialization.
More Information
  • Author Bio:

    Xue-Li Sun received her B.S. degree from Zhoukou Normal University, Zhoukou, in 2016, and her M.S. degree from Fujian Normal University, Fuzhou, in 2019, both in mathematics. She is currently working toward her Ph.D. degree in computer science at the Soochow University, Suzhou. Her research interests include interconnection networks, graph theory, parallel and distributed systems, fault diagnosis and fault-tolerant computing

    Jian-Xi Fan received his B.S. degree in computer science from Shandong Normal University, Jinan, in 1988, his M.S. degree in computer science from Shandong University, Jinan, in 1991, and his Ph.D. degree in computer science from the City University of Hong Kong, Hong Kong, in 2006. He is currently a professor with the School of Computer Science and Technology, Soochow University, Suzhou. He visited as a senior research fellow with the Department of Computer Science, City University of Hong Kong from May 2012 to August 2012. He has published more than 150 research papers in refereed journals and conferences, including IEEE Transactions on Parallel and Distributed Systems, IEEE Transactions on Computers, INFOCOM, and ICDCS. His research interests include parallel and distributed systems, interconnection architectures, data center networks, and graph algorithms

    Bao-Lei Cheng received his B.S., M.S. and Ph.D. degrees in computer science from Soochow University in 2001, 2004, 2014, respectively. He is currently an associate professor of computer science at School of Computer Science and Technology at Soochow University, Suzhou. His research interests include parallel and distributed systems, interconnection architectures, and software testing

    Yan Wang received her B.S. and M.S. degrees in computer science from Nanjing University of Aeronautics and Astronautics, Nanjing, in 1999 and 2002, respectively. She obtained her Ph.D. degree in computer science from Soochow University, Suzhou, in 2014. She is currently an associate professor of computer science at School of Computer Science and Technology, Soochow University, Suzhou. Her research interests include parallel and distributed systems, interconnection architectures, graph theory, and social networks

    Li Zhang received his B.S. and M.S. degrees in computer science and technology from Anhui Normal University, Wuhu, and Huaibei Normal University, Huaibei, in 2008 and 2011, respectively. He obtained his Ph.D. degree in computer science from Soochow University, Suzhou, in 2021. He is currently a lecturer at School of Information Engineering at the Yangzhou Polytechnic Institute, Yangzhou. His research interests include mobile crowd sensing, distributing computing, and mobile computing

  • Corresponding author:

    jxfan@suda.edu.cn

  • Received Date: October 20, 2020
  • Accepted Date: December 15, 2021
    Abstract

  • With the development of high-performance computing and the expansion of large-scale multiprocessor systems, it is significant to study the reliability of systems. Probabilistic fault diagnosis is of practical value to the reliability analysis of multiprocessor systems. In this paper, we design a linear time diagnosis algorithm with the multiprocessor system whose threshold is set to 3, where the probability that any node is correctly diagnosed in the discrete state can be calculated. Furthermore, we give the probabilities that all nodes of a d-regular and d-connected graph can be correctly diagnosed in the continuous state under the Weibull fault distribution and the Chi-square fault distribution. We prove that they approach to 1, which implies that our diagnosis algorithm can correctly diagnose almost all nodes of the graph.

    • FullText(HTML)
    • References (23)
  • [1]
    Somani A K, Agarwal V K, Avis D. A generalized theory for system level diagnosis. IEEE Trans. Computers, 1987, C-36(5): 538–546. DOI: 10.1109/TC.1987.1676938.
    [2]
    Preparata F P, Metze G, Chien R T. On the connection assignment problem of diagnosable systems. IEEE Trans. Electronic Computers, 1967, EC-16(6): 848–854. DOI: 10.1109/PGEC.1967.264748.
    [3]
    Chang N W, Hsieh S Y. Structural properties and conditional diagnosability of star graphs by using the PMC model. IEEE Trans. Parallel and Distributed Systems, 2014, 25(11): 3002–3011. DOI: 10.1109/TPDS.2013.290.
    [4]
    Li X Y, Fan J X, Lin C K, Cheng B L, Jia X H. The extra connectivity, extra conditional diagnosability and t/k-diagnosability of the data center network DCell. Theoretical Computer Science, 2019, 766: 16–29. DOI: 10.1016/j.tcs.2018.09.014.
    [5]
    Li X Y, Fan J X, Lin C K, Jia X H. Diagnosability evaluation of the data center network DCell. The Computer Journal, 2018, 61(1): 129–143. DOI: 10.1093/comjnl/bxx 057.
    [6]
    Lin L M, Huang Y Z, Wang X D, Xu L. Restricted connectivity and good-neighbor diagnosability of split-star networks. Theoretical Computer Science, 2020, 824-825: 81–91. DOI: 10.1016/j.tcs.2020.04.015.
    [7]
    Lv M J, Fan J X, Zhou J Y, Cheng B L, Jia X H. The extra connectivity and extra diagnosability of regular interconnection networks. Theoretical Computer Science, 2020, 809: 88–102. DOI: 10.1016/j.tcs.2019.12.001.
    [8]
    Wang S Y, Wang Z H, Wang M J S, Han W P. g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model. Frontiers of Mathematics in China, 2017, 12(5): 1221–1234. DOI: 10.1007/s11464-017-0657-9.
    [9]
    Zhu Q, Zhang J, Li L L. The h-extra connectivity and h-extra conditional diagnosability of bubble-sort star graphs. Discrete Applied Mathematics, 2018, 251: 322–333. DOI: 10.1016/j.dam.2018.03.077.
    [10]
    Xu X, Zhou S M, Xu L. Diagnosabilities of regular networks under three-valued comparison models. International Journal of High Performance Computing and Networking, 2017, 10(4/5): 251–258. DOI: 10.1504/IJHPCN.2017.086529.
    [11]
    Liang J R, Feng H, Du X J. Intermittent fault diagnosability of interconnection networks. Journal of Computer Science and Technology, 2017, 32(6): 1279–1287. DOI: 10.1007/s11390-017-1800-5.
    [12]
    Sun X L, Zhou S M, Lv M J, Liu J F, Lian G Q. Intermittent fault diagnosability of some general regular networks. The Computer Journal, 2020, 63(1): 16–24. DOI: 10.1093/comjnl/bxy128.
    [13]
    Blough D M, Sullivan G F, Masson G M. Efficient diagnosis of multiprocessor systems under probabilistic models. IEEE Trans. Computers, 1992, 41(9): 1126–1136. DOI: 10.1109/12.165394.
    [14]
    Fussell D, Rangarajan S. Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity. In Proc. the 19th International Symposium on Fault-Tolerant Computing. Digest of Papers, Jun. 1989, pp.560–565. DOI: 10.1109/FTCS.1989.105636.
    [15]
    Tang Q Y, Song X Y. Diagnosis of parallel computers arbitrary connectivity. IEEE Trans. Computers, 1999, 48(7): 757–761. DOI: 10.1109/12.780885.
    [16]
    Rangarajan S, Fussell D. Diagnosing arbitrarily connected parallel computers with high probability. IEEE Trans. Computers, 1992, 41(5): 606–615. DOI: 10.1109/12.142687.
    [17]
    Huang K Y, Agarwal V K, Thulasiraman K. Diagnosis of clustered faults and wafer testing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(2): 136–148. DOI: 10.1109/43.681263.
    [18]
    Tang Q Y, Song X Y, Wang Y K. Diagnosis of clustered faults for identical degree topologies. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1999, 18(8): 1192–1201. DOI: 10.1109/43.775637.
    [19]
    Lu X J, Li J P, Seo C J. Probabilistic diagnosis of clustered faults for shared structures. Mathematical and Computer Modelling, 2009, 49(3/4): 623–634. DOI: 10.1016/j.mcm.2008.06.011.
    [20]
    Lv M J, Zhou S M, Sun X L, Lian G Q, Liu J F, Wang D J. Probabilistic diagnosis of clustered faults for hypercube-based multiprocessor system. Theoretical Computer Science, 2019, 793: 113–131. DOI: 10.1016/j.tcs.2019.06.023.
    [21]
    Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Computers, 1989, 38(4): 555–566. DOI: 10.1109/12.21148.
    [22]
    Compeau P E C. Girth of pancake graphs. Discrete Applied Mathematics, 2011, 159(15): 1641–1645. DOI: 10. 1016/j.dam.2011.06.013.
    [23]
    Song S L, Zhou S M, Li X Y. Conditional diagnosability of burnt pancake networks under the PMC model. The Computer Journal, 2016, 59(1): 91–105. DOI: 10.1093/ comjnl/bxv066.
    • Relative Articles

  • Related Articles

    [1]Xiao-Qing Liu, Shu-Ming Zhou, Eddie Cheng, Hong Zhang. The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models[J]. Journal of Computer Science and Technology, 2024, 39(5): 1207-1222. DOI: 10.1007/s11390-024-2732-5
    [2]Jia-Yu Liu, Fei Wang, Hai-Ping Ma, Zhen-Ya Huang, Qi Liu, En-Hong Chen, Yu Su. A Probabilistic Framework for Temporal Cognitive Diagnosis in Online Learning Systems[J]. Journal of Computer Science and Technology, 2023, 38(6): 1203-1222. DOI: 10.1007/s11390-022-1332-5
    [3]Chen Fu, Andrea Turrini, Xiaowei Huang, Lei Song, Yuan Feng, Li-Jun Zhang. Model Checking for Probabilistic Multiagent Systems[J]. Journal of Computer Science and Technology, 2023, 38(5): 1162-1186. DOI: 10.1007/s11390-022-1218-6
    [4]Yu-Ting Qiang, Yan-Wei Fu, Xiao Yu, Yan-Wen Guo, Zhi-Hua Zhou, Leonid Sigal. Learning to Generate Posters of Scientific Papers by Probabilistic Graphical Models[J]. Journal of Computer Science and Technology, 2019, 34(1): 155-169. DOI: 10.1007/s11390-019-1904-1
    [5]Jia-Rong Liang, Hao Feng, Xiaojiang Du. Intermittent Fault Diagnosability of Interconnection Networks[J]. Journal of Computer Science and Technology, 2017, 32(6): 1279-1287. DOI: 10.1007/s11390-017-1800-5
    [6]Nan Ding, Shu-De Zhou, Zeng-Qi Sun. Histogram-Based Estimation of Distribution Algorithm: A Competent Method for Continuous Optimization[J]. Journal of Computer Science and Technology, 2008, 23(1): 35-43.
    [7]MA Zongmin, ZHANG W. J, MA W. Y. Extending the Relational Model to Deal with Probabilistic Data[J]. Journal of Computer Science and Technology, 2000, 15(3): 230-240.
    [8]SHEN Yidong. A Theory of Hybrid Diagnosis[J]. Journal of Computer Science and Technology, 1999, 14(4): 363-371.
    [9]Gu Junzhong. An Object-Oriented Transaction Model[J]. Journal of Computer Science and Technology, 1993, 8(4): 3-20.
    [10]Guo Hengchang. On the Characterization and Fault Identification of Sequentially t-Diagnosable System Under PMC Model[J]. Journal of Computer Science and Technology, 1991, 6(1): 83-90.
    • Supplements (3)

  • Others

  • Cited by

    Periodical cited type(1)

    1. Zhipeng Zhao, Zhenyu Hu, Zhiyu Zhao, et al. Fault-tolerant Hamiltonian cycle strategy for fast node fault diagnosis based on PMC in data center networks. Mathematical Biosciences and Engineering, 2024, 21(2): 2121. DOI:10.3934/mbe.2024093

    Other cited types(0)

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (165) PDF downloads (17) Cited by(1)
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return