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 stra...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.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.61977016 and 61572010the Natural Science Foundation of Fujian Province of China under Grant Nos.2023J01539 and 2020J01164the 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.
