The t/k-diagnosability for regular networks

Limei Lin, Li Xu, Shuming Zhou, Sun Yuan Hsieh

研究成果: Article同行評審

21 引文 斯高帕斯(Scopus)


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≥ 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≥ 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≥ 2m) or O(Nm) (when N< 2m) 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≤ k≤ 3) of some regular networks, including an n -dimensional alternating group graph, an n -dimensional Split-Star Network, a ln -hypermesh and an (n,l) -star graph, which are well-known interconnection networks proposed for multiprocessor systems.

頁(從 - 到)3157-3170
期刊IEEE Transactions on Computers
出版狀態Published - 2016 十月 1

All Science Journal Classification (ASJC) codes

  • 軟體
  • 理論電腦科學
  • 硬體和架構
  • 計算機理論與數學


深入研究「The t/k-diagnosability for regular networks」主題。共同形成了獨特的指紋。