Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (6A): 240700180-9.doi: 10.11896/jsjkx.240700180

• Computer Software & Architecture • Previous Articles     Next Articles

Study on t/s Diagnosability and t/s Diagnostic Algorithm of (n,k)-Arrangement Graphs

ZHANG Shihao1, LENG Ming2   

  1. 1 University School of Software Work,Jiangxi University of Science and Technology,Nanchang 330013,China
    2 Department of Computer Science,Jinggangshan University,Ji'an,Jiangxi 343009,China
  • Online:2025-06-16 Published:2025-06-12
  • About author:ZHANG Shihao,born in 2001,postgra-duate.His main research interests include fault diagnosis of network systems and so on.
    LENG Ming,born in 1975,Ph.D,professor,postgraduate supervisor.His main research interests include fault diagnosis,algorithm analysis and design,combination analysis and optimization, and so on.
  • Supported by:
    Jiangxi Provincial Natural Science Foundation(20202BABL202042),National Natural Science Foundation of China(62262032,61862035,61562046) and Science and Technology Plan Projects of the Education Department of Jiangxi Province(GJJ2201604,GJJ201033,GJJ211037).

PDF (PC)

33

Abstract: Given the increasingly severefault risks in multiprocessor systems,particularly in the field of supercomputers,enhancing system reliability and fault tolerance has emerged as a critical issue that requires urgent attention.In response to this need,the(n,k)-arrangement graph,as a novel interconnect network topology,has arisen.It is a generalization and variation of the star graph network,inheriting its inherent symmetry and fault tolerance while offering greater flexibility.However,the current research on the reliability of the(n,k)-arrangement graph is still incomplete.Based on this,exploring the t/s diagnosability and t/s diagnosis algorithm of the(n,k)-arrangement graph.Initially,we present a series of relevant topological properties.Subsequently,we prove the t/s diagnosability of the(n,k)-arrangement graph under the PMC model.Finally,we design a fast diagnosis algorithm with a time complexity of O(N log2N) to identify faulty nodes within the(n,k)-arrangement graph.The diagnosability of (n,k)-arrangement graphshavebeen identified,further refining the reliability metrics of (n,k)-arrangement graph networks,thereby offering crucial reliability performance criteria for their application and promotion.

Key words: Reliability, t/s diagnosability, t/s diagnostic algorithm, (n,k)-arrangement graph, PMC model

CLC Number: 

  • TP393
[1]FRIEDMAN A D,SIMONCINI L.System-level fault diagnosis[J].Computer,1980,13(3):47-53.
[2]SEERA M,LIM C P,ISHAK D,et al.Fault detection and diagnosis of induction motors using motor current signature analysis and a hybrid FMM-CART model[J].IEEE Trans on Neural Networks and Learning Systems,2011,23(1):97-108.
[3]FAN J,JIA X.Edge-pan cyclicity and path-embeddability of bijective connection graphs[J].Information Sciences,2008,178(2):340-351.
[4]FAN J,JIA X,LIU X,et al.Efficient unicast in bijective connection networks with the restricted faulty node set[J].Information Sciences,2011,181(11):2303-2315.
[5]PRETARATA F P,METZE G,CHIEN R T.On the connection assignment problem of diagnosis systems[J].IEEE Transactions on Computers,1967,16(12):848-854.
[6]MALEK M.A comparison connection assignment for diagnosisof multiprocessor systems [C]//Proc of the 7th annual symposium on Computer Architecture.New York:Association for Computing Machinery,1980:31-36.
[7]SENGUPTA A,DAHBURA A T.On self-diagnosable multi-processor systems:diagnosis by the comparisonapproach[J].IEEE Transactions on Computers,1992,41(11):1386-1396.
[8]PENG S L,LIN C K,TAN J J,et al.The g-good-neighbor conditional diagnosability of hypercube under PMC model.AppliedMathematics and Computation[J],2012,218(21):10406-10412.
[9]SY C N H.Conditional diagnosability of augmented cubes under the PMC model[J].IEEE Trans Dependable Secure Compute,2012,9(1):46.
[10]LAI P L,TAN J J,CHANG C P,et al.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers,2005,54(2):165-175.
[11]JUN Y,AIXIA L,XUE M,et al.The g good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model[J].IEEE Trans.Parallel Diatribe.Syst.,2015,26:1165-1177.
[12]SENGUPTA A,DAHBURA A T.On self-diagnosable multi-processor systems:diagnosis by the comparison approach[J].IEEETrans on Computers,1992,41(11):1386-1396.
[13]YANG X,TANG Y Y.Efficient fault identification of diagnosable systems under the comparison model[J].IEEE Transactions on computers,2007,56(12):1612-1618.
[14]HSIEH S Y,CHEN Y S.Strongly diagnosable product networks under the comparison diagnosis model[J].IEEE Transactions on Computers,2008,57(6):721-732.
[15]LAI P L.A systematic algorithm for identifying faults on hypercube-like networks under the comparison model[J].IEEE Transactions on Reliability,2012,61(2):452-459.
[16]ZHENG J,LATIFI S,REGENTOVA E,et al.Diagnosability of star graphs under the comparison diagnosis model[J].Information Processing Letters,2005,93(1):29-36.
[17]FRIEDMA N,ARTHUR D.A new measure of digital systemdiagnosis [C]//Proceedings Int.Symp.Fault-Tolerant Computing.1975:167-170.
[18]LIANG J,ZHANG Q,LI H.Structural properties and t/s-diagnosis for star networks based on the PMC model[J].IEEE Access,2017,5:26175-26183.
[19]LIANG J,ZHANG Q.The t/s-diagnosability of hypercube networks under the PMC and comparison models[J].IEEE Access,2017,5:5340-5346.
[20]LIN Y,LIN L,HUANG Y,et al.The t/s-diagnosability and t/s-diagnosis algorithm of folded hypercube under the PMC/MM* model[J].Theoretical Computer Science,2021,887:85-98.
[21]XIE Y,LIANG J,YIN W,et al.The properties and t/s-diagnosability of k-ary n-cube networks[J].The Journal of Supercomputing,2022,78(5):7038-7057.
[22]AKERS S B, KRISHNAMURTHY B.A group-theoretic model for symmetric interconnection networks[J].IEEE trans on Computers,1989,38(4):555-566.
[23]DAY K, TRIPATHI A.Arrangement graphs:a class of genera-lized star graphs[J].Information Processing Letters,1992,42(5):235-241.
[24]ZHOU S,XU J M.Fault diagnosability of arrangement graphs[J].Information Sciences,2013,246:177-190.
[25]LIN L, ZHOU S.Conditional connectivity for(n,k)-arrange-ment graphs [J].Math.Study,2012,45(4):350-364.
[26]GUO C,XIAO Z F,LENG M,et al.(t,k)-diagnosability of exchanged crossed cube under the PMC model[J].Journal on Communications,2019,40(6):190-202.
[27]LIANG J R,CHEN M J.Research on (t,k)-diagnosability for ugmented cube network under the comparison model[J].Journal on Communications,2017,38(8):9-18.
[28]YIN W,LIANG J,XIE Y,et al.The t/k-diagnosability of m-ary n-cube networks[J].Theoretical Computer Science,2024,986:114345.
[29]SUN X,FAN J,CHENG B,et al.The t/m-diagnosis strategy of augmented k-ary n-cubes[J].Theoretical Computer Science,2023,945:113671.
[1] JIN Jiaobo, ZHU Tiantian. Circuit Module Reliability Calculation Method for Multi-target Tracking [J]. Computer Science, 2025, 52(6A): 240800094-6.
[2] ZHANG Ce, SUN Zhichao, JI Kexing, WANG Jinyong, WANG Yubin. Modeling Mechanism and Review of Imperfect Debugging Reliability Model Related to the Total Number of Faults in Software [J]. Computer Science, 2025, 52(6): 21-34.
[3] TU Yuanjie, CHENG Baolei, WANG Yan, HAN Yuejuan, FAN Jianxi. g-Good-Neighbor Conditional Diagnosability and g-Extra Conditional Diagnosability of Hypercubes Under Symmetric PMC Model [J]. Computer Science, 2024, 51(9): 103-111.
[4] WANG Tian, SHEN Wei, ZHANG Gongxuan, XU Linli, WANG Zhen, YUN Yu. Soft Real-time Cloud Service Request Scheduling and Multiserver System Configuration for ProfitOptimization [J]. Computer Science, 2024, 51(6A): 230900099-10.
[5] LIANG Jingyu, MA Bowen, HUANG Jiwei. Reliability-aware VNF Instance Placement in Edge Computing [J]. Computer Science, 2024, 51(6A): 230500064-6.
[6] ZHANG Hao, GUO Oufan, ZHOU Feifei, MA Tao, HE Yingli, YAO Subin. Study on Dynamic Redundancy Mechanism of Time Sensitive Networks Based on Segmented Frame Copy and Elimination [J]. Computer Science, 2024, 51(11A): 240300085-7.
[7] BING Ying’ao, WANG Wenting, SUN Shengze, LIU Xin, NIE Qigui, LIU Jing. Network Reliability Analysis of Power Monitoring System Based on Improved Fuzzy ComprehensiveEvaluation Method [J]. Computer Science, 2023, 50(6A): 220400293-7.
[8] LI Honghui, CHEN Bo, LU Shuyi, ZHANG Junwen. Study on Reliability Prediction Model Based on BASFPA-BP [J]. Computer Science, 2023, 50(5): 31-37.
[9] WEN Haolin, DI Peng, CHEN Tong. Design of Ship Mission Reliability Simulation System Based on Agent [J]. Computer Science, 2023, 50(11A): 220800272-7.
[10] LI Jinliang, LIN Bing, CHEN Xing. Reliability Constraint-oriented Workflow Scheduling Strategy in Cloud Environment [J]. Computer Science, 2023, 50(10): 291-298.
[11] XU Miaomiao, CHEN Zhenping. Incentive Mechanism for Continuous Crowd Sensing Based Symmetric Encryption and Double Truth Discovery [J]. Computer Science, 2023, 50(1): 294-301.
[12] ZHANG Zhi-long, SHI Xian-jun, QIN Yu-feng. Diagnosis Strategy Optimization Method Based on Improved Quasi Depth Algorithm [J]. Computer Science, 2022, 49(6A): 729-732.
[13] WANG Xin, ZHOU Ze-bao, YU Yun, CHEN Yu-xu, REN Hao-wen, JIANG Yi-bo, SUN Ling-yun. Reliable Incentive Mechanism for Federated Learning of Electric Metering Data [J]. Computer Science, 2022, 49(3): 31-38.
[14] WANG Bo, HUA Qing-yi, SHU Xin-feng. Study on Anomaly Detection and Real-time Reliability Evaluation of Complex Component System Based on Log of Cloud Platform [J]. Computer Science, 2022, 49(12): 125-135.
[15] BAO Chun-hui, ZHUANG Yi, GUO Li-ye. SDN Oriented Mobile Network Reliability Evaluation Algorithm [J]. Computer Science, 2022, 49(11A): 211000080-8.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.