The -Diagnosability for Regular Networks
Limei Lin, Li Xu, Shuming Zhou, Sun‐Yuan Hsieh · IEEE Transactions on Computers · 2015
The$t/k$-diagnosis strategy can significantly enhance the system’s self-diagnosing capability at the expense of no more than$k$fault-free processors (vertices) being mistakenly diagnosed as faulty under the PMC model. It is a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis on multiprocessor systems. It can detect up to$t$faulty processors (vertices) which might include at most$k$misdiagnosed processors (vertices), where$k$is typically a small number. In the case$k\ge 1$, to our knowledge, there is no known$t/k$-diagnosis algorithm for general regular networks. In this paper, we first propose a general$t/k$-diagnosis ($k\ge 1$) algorithm for some$m$-regular networks. These$m$-regular networks satisfying some conditions could establish the$t/k$-diagnosis algorithm, say$t/k$-$G$-$DIAG$, to determine the$t/k$-diagnosability. The complexity of this algorithm is only$O(N\log N)$(when$N\ge 2^m$) or$O(Nm)$(when$N< 2^m$) where$N$is the number of vertices in the network. Second, we present a complete proof that the network$G$is actually$t/k$-diagnosable. Finally, we establish the$t/k$-diagnosability ($1\le k\le 3$) of some regular networks, including an$n$-dimensionalalternating group graph, an$n$-dimensionalSplit-Star Network, a$l^n$-hypermeshand an$(n,l)$-star graph, which are well-known interconnection networks proposed for multiprocessor systems.