The Component Diagnosability of Hypercubes with Large-Scale Faulty Nodes. (14th December 2020)

• Record Type: Journal Article
• Authors: Zhang, Shurong; Liang, Dongyue; Chen, Lin; Li, Ronghua; Yang, Weihua
• Is Part Of: Computer journal. Volume 65:Number 5(2022)
• Page Start: 1129
• Page End: 1143
• Publication Date: 2020-12-14
• Subjects: diagnosis -- component diagnosability -- hypercubes -- reliability; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa155
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The diagnosability is one of the most important measures of the reliability of networks. Consider the setting where there are large-scale failures that disconnect the network and result in many components. Then, the diagnosability is closely related to the number of components. In this paper, we define and study the $\boldsymbol{g}$ -component diagnosability of network $\boldsymbol{G}$, which is denoted by $\boldsymbol{ct_g(G)}$ and has not been addressed before. $\boldsymbol{ct_g(G)}$ is the maximum number of nodes in the faulty node set $\boldsymbol{F}$ of $\boldsymbol{G}$ such that $\boldsymbol{G-F}$ has at least $\boldsymbol{g}$ components and diagnosis model can identify all nodes in $\boldsymbol{F}$ . Under PMC and MM$^*$ diagnosis models, we show that, in the hypercube $\boldsymbol{Q_n\ (n\geq 7)}$, $\boldsymbol{ct_{g+1}(Q_n)=-(1/2)g^2+(n-3/2)g+n}$ when $\boldsymbol{g\leq n-1}$ . Moreover, we determine the $\boldsymbol{(n+1)}$ -component diagnosability $\boldsymbol{ct_{n+1}(Q_n)=n^2/2+n/2-2}$ for $\boldsymbol{n\geq 7}$ .