TY - JOUR

T1 - A Pessimistic Fault Diagnosability of Large-Scale Connected Networks via Extra Connectivity

AU - Lin, Limei

AU - Huang, Yanze

AU - Xu, Li

AU - Hsieh, Sun Yuan

N1 - Funding Information:
The authors declare that there is no conflict of interest regarding the publication of this article. This work was supported in part by Fok Ying Tung Education Foundation under Grant 171061 and in part by the National Natural Science Foundation of China under Grants 61702100, U1905211, 61702103, and 61771140.
Publisher Copyright:
© 1990-2012 IEEE.

PY - 2022/2/1

Y1 - 2022/2/1

N2 - The t/kt/k-diagnosability and hh-extra connectivity are regarded as two important indicators to improve the network reliability. The t/kt/k-diagnosis strategy can significantly improve the self-diagnosing capability of a network at the expense of no more than kk fault-free nodes being mistakenly diagnosed as faulty. The hh-extra connectivity can tremendously improve the real fault tolerability of a network by insuring that each remaining component has no fewer than h+1h+1 nodes. However, there is few result on the inherent relationship between these two indicators. In this article, we investigate the reason that caused the serious flawed results in (Liu, 2020), and we propose a diagnosis algorithm to establish the t/kt/k-diagnosability for a large-scale connected network GG under the PMC model by considering its hh-extra connectivity. Let \kappa h(G)κh(G) be the hh-extra connectivity of GG. Then, we can deduce that GG is \kappa h(G)/hκh(G)/h-diagnosable under the PMC model with some basic conditions. All \kappa h(G)κh(G) faulty nodes can be correctly diagnosed in the large-scale connected network GG and at most hh fault-free nodes would be misdiagnosed as faulty. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. We will apply the newly found relationship to directly obtain the \kappa h(G)/hκh(G)/h-diagnosability of a series of well known networks, including hypercubes, folded hypercubes, balanced hypercubes, dual-cubes, BC graphs, star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, alternating group graphs, split-star networks, kk-ary nn-cubes and (n,k)(n,k)-star graphs.

AB - The t/kt/k-diagnosability and hh-extra connectivity are regarded as two important indicators to improve the network reliability. The t/kt/k-diagnosis strategy can significantly improve the self-diagnosing capability of a network at the expense of no more than kk fault-free nodes being mistakenly diagnosed as faulty. The hh-extra connectivity can tremendously improve the real fault tolerability of a network by insuring that each remaining component has no fewer than h+1h+1 nodes. However, there is few result on the inherent relationship between these two indicators. In this article, we investigate the reason that caused the serious flawed results in (Liu, 2020), and we propose a diagnosis algorithm to establish the t/kt/k-diagnosability for a large-scale connected network GG under the PMC model by considering its hh-extra connectivity. Let \kappa h(G)κh(G) be the hh-extra connectivity of GG. Then, we can deduce that GG is \kappa h(G)/hκh(G)/h-diagnosable under the PMC model with some basic conditions. All \kappa h(G)κh(G) faulty nodes can be correctly diagnosed in the large-scale connected network GG and at most hh fault-free nodes would be misdiagnosed as faulty. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. We will apply the newly found relationship to directly obtain the \kappa h(G)/hκh(G)/h-diagnosability of a series of well known networks, including hypercubes, folded hypercubes, balanced hypercubes, dual-cubes, BC graphs, star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, alternating group graphs, split-star networks, kk-ary nn-cubes and (n,k)(n,k)-star graphs.

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

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

U2 - 10.1109/TPDS.2021.3093243

DO - 10.1109/TPDS.2021.3093243

M3 - Article

AN - SCOPUS:85112098834

VL - 33

SP - 415

EP - 428

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 2

M1 - 9468369

ER -