The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models  

作　　者：Xiao-Qing Liu Shu-Ming Zhou Eddie Cheng Hong Zhang 柳晓青;周书明;Eddie Cheng;张红(College of Mathematics and Statistics,Fujian Normal University,Fuzhou 350117,China;Center for Applied Mathematics of Fujian Province,Fujian Normal University,Fuzhou 350117,China;Department of Mathematics and Statistics,Oakland University,Rochester,MI 48309,U.S.A)

机构地区：[1]College of Mathematics and Statistics,Fujian Normal University,Fuzhou 350117,China [2]Center for Applied Mathematics of Fujian Province,Fujian Normal University,Fuzhou 350117,China [3]Department of Mathematics and Statistics,Oakland University,Rochester,MI 48309,U.S.A

出　　处：《Journal of Computer Science & Technology》2024年第5期1207-1222,共16页计算机科学技术学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.61977016 and 61572010;the Natural Science Foundation of Fujian Province of China under Grant Nos.2023J01539 and 2020J01164;the Fujian Alliance of Mathematics under Grant No.2023SXLMMS04,and the China Scholarship Council under Grant No.202108350054.

摘　　要：Fault diagnosis plays a crucial role in the fault tolerability assessment of an interconnection network,which is of great value in the design and maintenance of large-scale multiprocessor systems.A t/s-diagnostic strategy,as the generalization of the t/t-diagnostic strategy,refers to the self-diagnosis of a multiprocessor system in which all faulty vertices can be identified in a set of size at most s in the presence of at most t faulty vertices.In this work,we show that the balanced hypercube BH_(n)(n≥4)is((2n+1)■g/2■-■g/2■^(2))/((2n+1)■g/2■-■g/2■^(2)+(g-2))-diagnosable under both the Preparata,Metze,and Chien(PMC)and MM^(*)models for 4≤■■g/2■≤n.Moreover,we propose two effective t/s-diagnosis algorithms under the PMC and MM^(*)models with time complexity O(NlogN)and O(N(logN)^(2))(N=2^(2n)is the order of BH_(n)),respectively.Finally,comparison results indicate that t/s-diagnosability strengthens the self-diagnosable capability of the system compared with traditional diagnosabilities.

关 键 词：fault diagnosis t/s-diagnosability t/s-diagnosis algorithm balanced hypercube 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]