TY - JOUR

T1 - The t/k-diagnosability for regular networks

AU - Lin, Limei

AU - Xu, Li

AU - Zhou, Shuming

AU - Hsieh, Sun Yuan

N1 - Funding Information:
This work is partly supported by the National Natural Science Foundation of China (No. 61572010, No. 61072080, No. U1405255), Natural Science Foundation of Fujian Province (No. 2013J01221, No. 2013J01222), Fujian Normal University Innovative Research Team (No. IRTL1207), and Hu Guozan Study-Abroad Grant for Graduates of Fujian Normal University. L. Xu is the corresponding author.

PY - 2016/10/1

Y1 - 2016/10/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84987639450&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84987639450&partnerID=8YFLogxK

U2 - 10.1109/TC.2015.2512866

DO - 10.1109/TC.2015.2512866

M3 - Article

AN - SCOPUS:84987639450

VL - 65

SP - 3157

EP - 3170

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 10

M1 - 7366747

ER -