In multiprocessor systems, fault diagnosis technology is a core mechanism for ensuring system reliability and efficient operation. This paper proposes a new diagnosability parameter (referred to as g-extra H-structure diagnosability) for structural faults that may occur in multiprocessor systems, based on the number of nodes within each component of the remaining part (i.e., the system after removing the faulty nodes). We use the graph G to represent a multiprocessor system. A graph G is said to be g-extra H-structure t-diagnosable if, for any two distinct g-extra H-structure fault sets <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$S_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$S_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$|S_1|\le t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msub> <mi>S</mi> <mn>1</mn> </msub> <mrow> <mo stretchy="false">|</mo> <mo>≤</mo> <mi>t</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$|S_2|\le t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msub> <mi>S</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">|</mo> <mo>≤</mo> <mi>t</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation>, the vertex sets <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$V(S_1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <msub> <mi>S</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$V(S_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <msub> <mi>S</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are distinguishable under a given diagnosis model. The g-extra H-structure diagnosability of G, denoted by <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$t^g_s(G; H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mi>s</mi> <mi>g</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the maximum value of t such that G is g-extra H-structure t-diagnosable. This parameter refers to the maximum number of g-extra H-structure sets that the system can precisely detect by itself. The relationship between this parameter and the original H-structure diagnosability is also presented. Additionally, under the PMC and MM* diagnostic models, we determine <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$t_s^g(Q_n;K_{1,1})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mi>s</mi> <mi>g</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$t_s^g(Q_n;C_4)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mi>s</mi> <mi>g</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$g\in \{1,2,3\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$t_s^g(Q_n;K_{1,2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>t</mi> <mi>s</mi> <mi>g</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo>;</mo> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for hypercube <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$g\in \{1,2\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>.

The g-extra H-structure diagnosability for assessing structural fault quantity in multiprocessor systems

期刊论文
发表日期：

2026年5月12日

查看全文

Nengjin Zhuo,
Shumin Zhang,
Jou-Ming Chang,
Bo Zhu

摘要

In multiprocessor systems, fault diagnosis technology is a core mechanism for ensuring system reliability and efficient operation. This paper proposes a new diagnosability parameter (referred to as g-extra H-structure diagnosability) for structural faults that may occur in multiprocessor systems, based on the number of nodes within each component of the remaining part (i.e., the system after removing the faulty nodes). We use the graph G to represent a multiprocessor system. A graph G is said to be g-extra H-structure t-diagnosable if, for any two distinct g-extra H-structure fault sets $S_1$ $S_{1}$ and $S_2$ $S_{2}$ with $|S_1|\le t$ $| S_{1} | \leq t$ and $|S_2|\le t$ $| S_{2} | \leq t$ , the vertex sets $V(S_1)$ $V (S_{1})$ and $V(S_2)$ $V (S_{2})$ are distinguishable under a given diagnosis model. The g-extra H-structure diagnosability of G, denoted by $t^g_s(G; H)$ $t_{s}^{g} (G; H)$ , is the maximum value of t such that G is g-extra H-structure t-diagnosable. This parameter refers to the maximum number of g-extra H-structure sets that the system can precisely detect by itself. The relationship between this parameter and the original H-structure diagnosability is also presented. Additionally, under the PMC and MM* diagnostic models, we determine $t_s^g(Q_n;K_{1,1})$ $t_{s}^{g} (Q_{n}; K_{1, 1})$ and $t_s^g(Q_n;C_4)$ $t_{s}^{g} (Q_{n}; C_{4})$ for $g\in \{1,2,3\}$ $g \in {1, 2, 3}$ , and $t_s^g(Q_n;K_{1,2})$ $t_{s}^{g} (Q_{n}; K_{1, 2})$ for hypercube $Q_n$ $Q_{n}$ with $g\in \{1,2\}$ $g \in {1, 2}$ .