# Two-Round Diagnosability Measures for Multiprocessor Systems

Authors: Jiarong Liang; Qian Zhang; Changzhen Li
Journal: Complexity
 (2020)

---

## Abstract

In a multiprocessor system, as a key measure index for evaluating its reliability, diagnosability has attracted lots of attentions. Traditional diagnosability and conditional diagnosability have already been widely discussed. However, the existing diagnosability measures are not sufficiently comprehensive to address a large number of faulty nodes in a system. This article introduces a novel concept of diagnosability, called two-round diagnosability, which means that all faulty nodes can be identified by at most a one-round replacement (repairing the faulty nodes). The characterization of two-roundt-diagnosable systems is provided; moreover, several important properties are also presented. Based on the abovementioned theories, for the n-dimensional hypercube Qn, we show that its two-round diagnosability is n2+n/2, which is n+1/2 times its classic diagnosability. Furthermore, a fault diagnosis algorithm is proposed to identify each node in the system under the PMC model. For Qn, we prove that the proposed algorithm is the time complexity of On2n.


---

## Body

## 1. Introduction

With the growth of the large scale integration technology, a huge number of multiprocessors are integrated to a multiprocessor computer system. It is not difficult to predict that, in such a system, some faulty processors (nodes) will be produced. To make sure that the system works properly, the designers should consider the problem that the system needs to have the ability to diagnose itself faulty processors such that they can be repaired or replaced with the new fault-free processors. In dealing with the problem of fault diagnosis for multiprocessor systems, two approaches are used: one is the system-level approach and another is the logic-circuit-level approach. Since the system-level approach is helpful for user-transparent reconfiguration, automatic, and recovery in the multiprocessor system while the logic-circuit approach is not, the designers prefer to design the system into a system-level fault-diagnosis system. In 1967, Preparata et al. proposed an automatic diagnosis procedure in multiprocessor systems, which is known as the first system-level diagnosis approach [1, 2]. This model proposed by Preparata et al. [1] is called the Preparata, Metze, and Chien (PMC) model. In theory, a digraph G=V,E can usually be used to denote a PMC model, where for two processors i and j, i,j∈E if and only if processor u is tested processor i. For each testing edge i,j, we can use 1 or 0 to denote their test result σi,j, where σi,j=1 implies that i judges j to be faulty and σi,j=0 implies that i judges j to be fault-free.There are several fundamental system-level diagnosis strategies:t-diagnosis, t/s-diagnosis s≥t and conditional t-diagnosis. Suppose that a system S has at most t faulty nodes, if each node in the system can be diagnosed correctly as either fault-free or faulty, then the system is called a t-diagnosable system; some research results on a t-diagnosable system can be found in [1–4], etc. In theory, the t-diagnosis approach is a key measurement for the reliability of considered network system. Besides, the t-diagnosis approach is desirable to be applied to the areas being related to network control, for example, in the research on reinforcement learning and adaptive optimization, we know that the neural network is often used to represent actor network and chosen as a optimal control policy [5]. Before an adaptive optimal controller is designed, it is necessary and important to test whether the nodes (neurons) in the neural network are fault-free or faulty by the t-diagnosis approach. For a system having at most t faulty nodes, if it can determine a set with the size ss≤t that contains all its faulty nodes, then it is t/s-diagnosable. Numerous studies have been reported on a t/s-diagnosable system, such as [6–12].In a system, denoted byG=V,E, with at most t faulty nodes, a subset Vi⊂V with Vi≤t is called a conditional faulty set if there does not exist a node v such that Nv⊂Vi, where Nv is a set consisting of all v′s neighbors. If for any two conditional faulty sets V1 and V2 with V1≠V2, σV1∩σV2=ϕ, where σVi is the set of syndromes produced by Vi, then the system is called conditionally t-diagnosable. Lots of efforts are made to study the conditionally t-diagnosable system, see [13–22].It is worth mentioning that the above three strategies are one-round diagnosis strategies, whose diagnosabilities are usually not too large. For instance,Qn is shown to be n-diagnosable and its t/t-diagnosability and conditional diagnosability are n and 2n−2/2n−2, respectively, based on the PMC model. However, when the size of the faulty node set is larger than the diagnosability of the above diagnosis strategies, the above diagnosable systems can do little for the diagnosis. Therefore, to address the issue that a system has a large number of faulty nodes, Chen et al. introduced a novel strategy, called by t/k-diagnosis, for the star network [23], where 1≤k≤t. A t/k-diagnosable system guarantees to identify at least k faulty nodes only if as long as the size of the set consisting of faulty nodes in it does not exceed t. Although a t/k-diagnosis has a large diagnosability, it takes much longer to repair faulty nodes, which leads to low efficiency. Therefore, it provides strong motivation for the study of a diagnosis strategy that can reach a balance between improving the diagnosability and being highly efficient. This paper presents a novel diagnosis approach, called by two-round t-diagnosis. Using the two-round t-diagnosis approach, the system can guarantee that each faulty node can be diagnosed by at most a one-round replacement (repairing the faulty nodes).A simple introduction on this paper’s remainder is as follows. Some related notations and definitions are presented as the preliminaries in Section2. In Section 3, two-round t-diagnosable systems are characterized and several important properties are also presented. In Section 4, the properties of a two-round t-diagnosable system is applied for computing the two-round t-diagnosability of Qn. In Section 5, a fast two-round diagnosis algorithm, whose time complexity is On2n, is proposed for Qn. Section 6 draws the conclusions.


## 2. Preliminaries

In the section, we introduce some necessary notations and definitions that are frequently used in the rest of the paper.Under the PMC model, for a system given by graphG=V,E, let Γx=yx,y∈Eandx,y∈V and Γ−1x=yy,x∈Eandx,y∈V. Similarly, for any subset X⊂V, ΓX=∪x∈XΓx−X and Γ−1X=∪x∈XΓ−1x−X. In particular, if G is undirected, then Γx=Γx−1=Nx and ΓX=ΓX−1=NX, where X⊂V.Definition 1.
Suppose thatG=V,E is a graph and has k connected components, say C1,C2,…,Ck. Then, CsubG=C1,C2,…,Ck is called a connected subgraph set of G. In particular, if G is connected, then CsubG=G. Additionally, let maxCsubG=Ci, where VCi≥VCj for each Cj∈CsubG.Definition 2.
LetG=V,E denote a graph and X⊂V. Then, GX=X,E¯ is called the induced subgraph by X, where E¯=u,vu,v∈E,u,v∈X.Definition 3.
LetG=V,E denote a graph, let CardkCsubG=CC∈CsubGandVC=k be the set of connected subgraphs with k nodes in G.For instance, for graphG shown in Figure 1, CsubG=C1,C2, where C1=Gv2,v3,v6, C2=Gv1,v4,v5,v7, Card3CsubG=Gv2,v3,v6, and Card4CsubG=Gv1,v4,v5,v7.Figure 1
A graph with 7 nodes.Definition 4.
LetG=V,E denote a system, M⊂V. For a given syndrome σ, if the following conditions are satisfied, then M⊂V is said to be an allowable fault set (AFS):(1)
σx,y=0, for any x,y∈V−M(2)
σx,y=1, for any x∈V−M and y∈MLemma 1.
Suppose thatG=V,E is a system and σ is a given syndrome. Let F1,F2⊆V be two AFSs, then F1∪F2 is also an AFS.Proof.
To the contrary, assume thatF1∪F2 is not an AFS; then, there exists at least one condition in Definition 4, which is not true.
If condition (1) is not true, then∃x,y∈V−F1∪F2 such that σx,y=1, a condition to F1 and F2 are two AFS.
If condition (2) is not true, then∃x∈V−F1∪F2 and y∈F1∪F2, where x,y∈E such that σx,y=0. If y∈F1, then F1 is not an AFS; if y∈F2, then F2 is not an AFS, which contradicts the hypothesis.Lemma 2.
For a given syndromeσ on the system G=V,E, suppose that G has k AFSs for σ, say F1,F2,…,Fk⊆V , then, ∩i=1kFi is the fault set of the system.Proof.
LetFc=∩i=1kFi. Let F be the maximal fault set, which exactly consists of all faulty nodes. We will show that F is an AFS for σ. To this end, let u,v∈E. u,v∈V−F implies that u and v are fault-free nodes, and then σu,v=0. Hence, condition (1) holds for F. For condition (2), u∈V−F and v∈F implies that u is a fault-free node and v is a faulty node and then that σx,y=1. Hence, condition (2) holds for F. Then, F is an AFS for σ. According to the assumption, we have that F∈F1,F2,…,Fk. So, Fc=∩i=1kFi⊆F.Definition 5.
LetG=V,E be a system, t an integer, X⊆V with 0<X<t. Suppose that X1,X2⊆V−X with X1∪X≤t and X2∪X≤t are two different subsets. X1,X2 is called a pair of distinguishable subsets of V−X if there exists an edge from X to X1ΔX2.According to Definition5, the following results are true. In the system G=V,E, if X⊆V with X<k, any two subsets X1⊆V−X with X1∪X≤t, X2⊆V−X with X2∪X≤t, and X1,X2 is a pair of distinguishable subsets in V−X, then the system can determine the fault set, provided that G has less than k faulty nodes and all faulty nodes in X have been repaired or replaced with additional fault-free nodes.Lemma 3.
Suppose that that the undirected graphG=V,E has less than t faulty nodes and G′⊂G with VG′≥t+1 is connected. If each result in G′ is 0, then G′ does not have faulty nodes.Proof.
To the contrary, letG′⊂G with VG′≥t+1 be connected, in which each result in it is 0 and there is a faulty node, say u. Then, it is clear that each node in NG′u is faulty. Similarly, each node in NG′NG′u is l faulty. As a result, each node VG′ is faulty. Note that VG′≥t+1; this implies that the number of fault nodes in G′ exceeds t, a contradiction. Therefore, each node in VG′ is fault-free.


## 3. Two-Roundt-Diagnosable Systems

At the beginning of the section, the concept of a two-roundt-diagnosable system is presented as follows.Definition 6.
A system is two-roundt-diagnosable if, for given syndrome σ, after repairing or replacing the faulty nodes identified by one-round diagnosis, the system can diagnose the remaining faulty nodes without replacement, provided that the system has less than t+1 faulty nodes.According to Definition6, we can obtain the following necessary conditions for a two-round t-diagnosable system.Theorem 1.
LetG=V,E represent a system. Then, G is two-round t-diagnosable if and only if for any a subset Y⊆V with Y≤t and any two distinct subsets Y1,Y2⊆V−Y, where Y∪Y1≤t,Y∪Y2≤t, and Y1∩Y2=ϕ, there exists at least an edge from V−Y1−Y2 to Y1ΔY2.Proof.
Necessity: since for anyY⊆V with Y=t, the result is trivial, next, we show that the result is true for the case of Y<t. To the contrary, suppose that there exists a subset Y⊆V, where Y<t and distinct subsets Y1,Y2⊆V−Y with Y∪Y1≤t,Y∪Y2≤t, Y1∩Y2=ϕ, such that there are no edges from V−Y1−Y2 to Y1ΔY2. Without loss of generality, suppose that each node in Y is faulty and G has more than Y faulty nodes. Define a syndrome σ as follows. Let x,y∈V with x,y∈E:(1)
Ifx,y∈V−Y−Y1−Y2, then σx,y=0(2)
Ifx∈V−Y−Y1−Y2 and y∈Y, then σx,y=1(3)
Ifx∈Y1−Y2 and y∈Y2−Y1, then σx,y=1(4)
Ifx∈Y2−Y1 and y∈Y1−Y2, then σx,y=1(5)
The remaining test results are arbitraryBothY∪Y1 and Y∪Y2 are allowable sets for syndrome σ. Suppose that F1,F2,…,Fk⊆V are all the allowable fault sets for σ. Let Fc=∩i=1kFi; Fc is a fault set of G and Fc⊆Y, which implies that the fault set Y1 identified by the first-round diagnosis is a subset of Y. Let G′ denote the system after replacing the nodes of Y1, and σ is a syndrome obtained by performing a test task on G′. Since there are no edges from V−Y1−Y2 to Y1ΔY2, then σx,y=σx,y=1 for x∈Y1−Y2,y∈Y2−Y1, and σx,y=σx,y=1 for x∈Y2−Y1,y∈Y1−Y2. Hence, both Y1 and Y2 are AFSs for σ, which is a contradiction to the hypothesis that G=V,E is two-round t-diagnosable.Sufficiency: for a syndromeσ, let Fc be the intersection of all AFSs for σ. According to Lemma 2, Fc is a fault set, where Fc≤t. If Fc=t, then each system has been diagnosed by syndrome σ, which implies that G is two-round t-diagnosable. If Fc<t, then let G′ denote the system for which all the nodes in Fc are repaired or replaced with additional fault-free nodes from G. Then, the number of faulty nodes in G′ will not be more than t−Fc, and these faulty nodes belong to V−Fc. Let σ denote a syndrome obtained by performing the test task to G′. We claim that the fault set Y1⊆V−Fc of G′ where Y1≤t−Fc can be determined by σ. In contrast, there exists another nonempty allowable subset Y2⊆V−Fc of G′, where Y2≤t−Fc for σ, and we derive a contradiction. Consider the following situations.Case 1: there is an edgex,y from V−Fc−Y1−Y2 to Y1ΔY2. Without loss of generality, let y∈Y1. Since Y2 is an allowable subset of V−Fc for σ, σx,y=0. On the contrary, since Y1 is a fault subset of V−Fc for σ, σx,y=1 is a contradiction.Case 2: there are no edges fromV−Fc−Y1−Y2 to Y1ΔY2. According to this assumption, there exists an edge x,y from Fc to Y1ΔY2. Without loss of generality, suppose that y∈Y1−Y2. Since Y2 is an allowable set for σ, σx,y=0. On the contrary, since Y1 is a fault set of G′, σx,y=1 is a contradiction. Hence, G is two-round t-diagnosable.
According to the proof of Theorem1, the two corollaries described as follows are obvious.Corollary 1.
A systemG=V,E is two-round t-diagnosable if for any subset Y⊆V with Y<t, and for any distinct disjoint subsets Y1,Y2⊆V−Y, where Y∪Y1≤t and Y∪Y2≤t, and Y1,Y2 is a pair of distinguishable subsets of V−Y.Definition 7.
LetS be a network system. The maximum nonnegative integer t that guarantees S to be two-round t-diagnosable is called the two-round diagnosability of S.For convenience, it is necessary to introduce a notationΓ2−1v=Γ−1v∪Γ−1Γ−1v−v for the coming corollary, where G=V,E is a system, v∈V.Corollary 2.
For the systemG=V,E, let α=minΓ2−1vv∈V+1. Then, the system is not two-round α-diagnosable.Proof.
Letv∈V be a node such that α=Γ2−1v+1. Consider the case such that F=Γ2−1v∪v is a fault set that consists of exactly all faulty nodes in the system. Note that F=α. Define a syndrome σ as follows. Let x,y∈V with x,y∈E (see Figure 2):(i)
Ifx,y∈V−Γ2−1v−v, then σx,y=0(ii)
Ifx∈V−Γ2−1v−v and y∈Γ−1Γ−1v−v, then σx,y=1 (before replacement)(iii)
Ifx∈Γ−1Γ−1v−v and y∈V−Γ2−1v−v, then σx,y=0(iv)
Ifx∈Γ−1Γ−1v−v and y∈Γ−1v, then σx,y=1(v)
Ifx∈Γ−1v, then σv,x=1(vi)
Ifx∈Γ−1Γ−1v−v, then σv,x=0(vii)
Ifx∈Γ−1v, then σv,x=1(viii)
Ifx∈Γ−1Γ−1v−v, then σv,x=1 (before replacement)(ix)
The other test results are arbitrary
Forσ, the nodes of subset Γ−1Γ−1v−v can be identified correctly as faulty, which implies that the nodes of subset Γ−1v∪v cannot be identified by syndrome σ. After the faulty nodes of subset Γ−1Γ−1v−v are repaired, there exist no edges from fault-free nodes to v, and the test results from v to faulty (fault-free) nodes are 1 (0), which implies that we cannot judge the state of node v. Therefore, to identify the state of node v, we need a second replacement. So, the system is not two-round α-diagnosable.Figure 2
A syndrome of Corollary2.


## 4. Two-Round Diagnosability of Hypercube Networks

Qn is a regular graph with 2n nodes and n2n edges. Each node in Qn can be denoted by an n-bit binary string. x,y∈EQn if and only if there is exactly different one bit position between x and y. Figure 3 is an illustration of a 4-dimensional hypercube network Q4.Figure 3
A 4-dimensional hypercube.Lemma 4.
(see [17]). Let X⊂VQn with Y=s and 0>s≤n+1. Then, the size of the neighbor set of Y is more than sn−ss+1/2.Lemma 5.
ForQn (n≥5), let S=vivi∈VQn,1≤i≤n,∩i=1nNvi=1. Then, NS=n2−n/2+1.Proof.
We useaddv to denote v′ address. Suppose that ∩i=1nNvi=v0 and addv0=a1a2⋯an. According to the definition of Qn, without loss of generality, assume that addv1=a1¯a2⋯an, addv2=a1a2¯⋯an,…,addvn=a1a2⋯an¯. For some i, we have that Nvi=a1¯a2⋯ai¯⋯an,a1a2¯a3⋯ai¯⋯an,…,a1a2⋯ai¯⋯an¯. Then, Nvi∩Nvj=v0,u, where addu=a1a2⋯ai¯⋯aj¯⋯an and 1≤i,j≤n,i≠j. So, NS=nn−1−Cn2+1=n2−nn+1/2+1=n2−n/2+1.
According to Lemmas4 and 5, for an n-dimensional hypercube and a subset S⊆V, where S=n+1, if ∃v∈S with Nv⊆S, then NS=n2−n/2.Lemma 6.
(see [19]). Suppose that Qn is modelled by a graph GV,En≥5. Let S⊂V with n≤S≤2n−1−1. If GV−S is disconnected and CsubGV−S=C1,C2,…,Cm, then the following conditions hold:(i)
Σi=01iCardiCsubGV−S≤1(ii)
There is uniqueCi∈CsubGV−S, where VCi≥2Lemma 7.
(see [24]). Suppose that Q5 is modelled by a graph GV,E. Let S⊂V with ≤5k−kk+1/21≤k≤4. If GV−S is disconnected and CsubGV−S=C1,C2,…,Cm, then the following conditions hold:(i)
Σi=0k−1iCardiCsubGV−S≤k−1(ii)
There is uniqueCi∈CsubGV−S, where VCi≥kLemma 8.
Letx>0 and y>0 are two integers. Then, x+y≤1+xy.Proof.
Consider the functiongx,y=1+xy−x+y. It is obvious that gx,y=x−1y−1. Since x≥1 and y≥1, then gx,y≥0, which implies that x+y≤1+xy.Lemma 9.
(see [24]). Suppose that Qn is modelled by a graph GV,En≥5. Let S⊂V with S≤kn−kk+1/21≤k≤n−1. If GV−S is disconnected and CsubGV−S=C1,C2,…,Cm, then the following conditions are true:(i)
Σi=0k−1iCardiCsubGV−S≤k−1(ii)
There is uniqueCi∈CsubGV−S, where VCi≥kLemma 10.
(see [24]). Suppose that Q5 is modelled by a graph GV,E. Let S⊂V with S≤9. If GV−S is disconnected and CsubGV−S=C1,C2,…,Cm, then the following conditions are true:(i)
Σi=0k−1iCardiCsubGV−S≤4(ii)
There is uniqueCi∈CsubGV−S, where VCi≥5Lemma 11.
(see [24, 25]). Suppose that Qn is modelled by a graph GV,En≥5. Let S⊂V with S≤n2−nn+1/2−1. If GV−S is disconnected and CsubGV−S=C1,C2,…,Cm, then the two conditions as follows are true:(i)
Σi=0n−1iCardiCsubGV−S≤n−2(ii)
There is uniqueCi∈CsubGV−S, where VCi≥nWith the above preliminaries, we shall discuss the two-round diagnosability ofQn.Theorem 2.
Ann-dimensional n≥6 hypercube given by G=V,E is not two-round n2+n/2+1-diagnosable.Proof.
Note that, for each nodev∈V, we have Γ2−1v∪v=n2+n/2+1 by Lemma 5. According to Corollary 2, it is easily determined that an n-dimensional hypercube is not two-round n2+n/2+1-diagnosable.Theorem 3.
Ann-dimensional n≥6 hypercube given by G=V,E is two-round n2+n/2-diagnosable.Proof.
LetX⊆V be a subset of V, where X<n2+n/2. According to Theorem 1, we will show that, for any two distinct subsets S1,S2⊆V−X, where X∪S1≤n2+n/2,X∪S2≤n2+n/2, and S1∩S2=ϕ, there exists at least an edge from V−S1−S2 to S1ΔS2. Without loss of generality, let S1−S2≠ϕ.
Now, consider the two situations:Case 1:X≥n2−n/2.Note thatS1<n2+n/2−|X|≤n2+n/2−n2−n/2=n and S2<n2+n/2−X≤n2+n/2−n2−n/2=n, which implies that S1−S2<n. Let k=S1−S2; then, 1≤k<n. According to Lemma 4, we have that NS1−S2≥kn−kk+1/2+1. Since fk=kn−kk+1/2+1 is an increasing function for k∈1,n−1/2, fk≥f1=n, which implies that S1−S2=fk>n>S2. Hence, there exists at least an edge from V−S1−S2 to S1−S2.Case 2:X<n2−n/2.To the contrary, assume that∃S1,S2⊆V−X with X∪S1≤n2+n/2,X∪S2≤n2+n/2, and S1∩S2=ϕ, but that there are no edges from V−S1−S2 to S1ΔS2. Next, we derive a contradiction. According to Lemma 11, we know that the system can be divided into three parts by a subset X (shown in Figure 4). Note that A is the largest component of GV−X, where A≥2n−n2−n/2−1−n−1=2n+2−n2+n/2, and B is the union of the remaining components of GV−X, where B≤n−1. Since B≤n−1 and Qn is a n-regular graph, S1∩B=ϕ. A similar argument can be used to obtain that S2∩B=ϕ. Hence, S1⊆A, and S2⊆A.
Note thatA−S1∪S2=A−S1−S2≥2n−X−S1−S2−n−1≥2n−3/2n2+n/2−n−1>0n≥6, and A is a component of V−S. This property implies that NS1ΔS2∩A≠ϕ, which is a contradiction.
In summary, we conclude thatQnn≥6 is two-round n2+n/2-diagnosable.As we know,Qn is n-diagnosable, 2n−2/2n−2-diagnosable, and conditionally 4n−7-diagnosable. A previous study has shown that Qn is also two-round n2+n/2-diagnosable. Figure 5 gives an intuitive comparison between these diagnosabilities for Qn.Figure 4
System divided intoA, B, and X by subset X.Figure 5
Comparison of the diagnosabilities ofQn between the traditional diagnosis approach and the two-round diagnosis approach.


## 5. A Fault Diagnosis Algorithm of Two Roundt-Diagnosable Hypercubes

In Section4, we observed that an n-dimensional hypercube (Qn) was two-round n2+n/2-diagnosable. Then, identifying all faults with at most a one-round replacement remains an open question. This section presents a fast identification algorithm to address this issue (Algorithm 1. The completeness of the identification algorithm is demonstrated, provided that the system has less than t+1 faulty nodes t≤n2−n/2−1. The fast identification algorithm is described in detail in Algorithm 2.Algorithm 1: Depth-first search.
Input:(i)
An undirected graphG=V,E with V=N representing a network system of interest and a network node x∈V. Let S=x.Output:A subsetS⊆V.(1)
DFSv:for eachu∈Nx,ifσy,x=σx,y=0,S=S∪y and DFSy.(2)
Output the node setS.Algorithm 2: Fast identification.
Input:An undirected graphG=V,E with V=2n, a positive integer tt≤n2−n/2−1 and a syndrome σ.(i)
Output:A fault setA, a fault-free node set B and a second-round fault set C, where A∪B∪C=V.(1)
LetSi=∅1≤i≤2n and B=A=C=∅.For anyui∈V−∪j=1iSi1≤i≤2n, perform DASui; SiDASui.whileSi≥t+1, let B=B∪Si, and A=A∪NB.(2)
WhileV=B∪A, output B and A. Otherwise, go to Step 3.(3)
WhileA≥t, let B=V−A, output B and A.Otherwise, repair the faulty nodes inA and executeBestA,B,C until B∪A∪C=V. Additionally, output subsets B, A, and C.BestA,B,C:For anyv∈V−A−B, if σu,v=1 (u∈A∪B), then C=C∪v; otherwise, B=B∪v.Algorithm1 is applied to each node of Qn with at most t faulty nodes (t≤n2−n/2−1). According to Lemmas 9 and 11, the unique set S can be output by Algorithm DFS, where S≥t+1.Theorem 4.
The time complexity of the fast identification algorithm isONlog2N, where N=2n.Proof.
For the sake of convenience, letF denote a set exactly consisting of faulty nodes in the system, L the largest component of the induced subgraph by V−F, and S a set consisting of all remaining small components in the induced subgraph by V−F. When ui∈L), Step 1 takes an amount of time equal to ONlog2N. When the ui∈S∪F, Step 1 takes an amount of time equal to On2+n/2+Nlog2N=ONlog2N. Hence, Step 1 takes an amount of time equal to ONlog2N. Step 2 and Step 3 take an amount of time equal to ON. So, the total time for Fast Identification is ONlog2N.
According to Lemmas9 and 11, the completeness of the fast identification algorithm is obvious, provided that Qn has no more than n2−n/2−1 faulty nodes. Note that Qn is two-round n2+n/2-diagnosable. Then, there is a question of whether our algorithm is suitable for the scenario in which there are tn2−n/2≤t≤n2+n/2 faults in the system. We perform a simulation to evaluate the system; in the following simulation, we assume that Qn has n2+n/2 faulty nodes, and each node of the system may be faulty with the same probability. We run our algorithm 1000 times. Table 1 gives the corresponding experimental results.
The simulation shows that our algorithm is suitable forQn, provided that it has no more than n2+n/2 faulty nodes.Table 1
Number of faulty nodes identified by the two-round algorithm applied to ann-dimensional hypercube.
n789101112Faults283645667891Identified faults283645667891


## 6. Conclusion

In this article, we introduce a novel diagnosis strategy called the two-round diagnosis strategy that implies that each node can be determined by at most a one-round replacement. A necessary and sufficient condition of the system being two-roundt-diagnosable is presented. Additionally, several important properties of this system are described. Using the theory of a two-round t-diagnosable system, we show that Qn is two-round n2+n/2-diagnosable. Compared to the traditional diagnosis strategy, the two-round diagnosability of Qn is n+1/2 times as large as n, the classic diagnosability of Qn. Furthermore, an On2n algorithm is provided to identify faulty nodes for Qn. The conditionally t-diagnosable network systems are a lass of typical nonlinear systems, in which the state (syndrome) of a node impacted these nodes in its surrounding area. Recent years, there are some studies to analyze nonlinear systems by using online policy iterative optimization algorithms [20, 26]. The combination of these algorithms and our algorithm will be a try to obtain an optimal fault set for considered conditionally t-diagnosable network system; this is one of our studies in the future.



---

*Source: 9535818-2020-06-24.xml*