1.   Introduction

With the vigorous development of computer communication technology, the scale of multiprocessor systems (the number of processors) is increasing. It is inevitable that some processors in such systems fail. Therefore, the fault diagnosis of processors becomes crucial. The most widely discussed system-level fault diagnosis of multiprocessor systems is mainly divided into two categories: deterministic fault diagnosis and uncertain fault diagnosis^[1]. Deterministic fault diagnosis can always absolutely and correctly complete the diagnosis task, that is, it requires that the test result of a fault-free node completely reflect the state of the tested node. The deterministic fault diagnosis model was first proposed by Preparata et al.^[2], called the PMC (Preparata Metze Chien) model, which has been widely studied^[3-9]. Under the PMC model, the outcome on the testing of a faulty node cannot be trusted while the outcome on the testing of a fault-free node is reliable (see Table 1). In an actual network, deterministic fault diagnosis may not necessarily be realized, such as the fault caused by the loss of test results^[10], and the intermittent fault caused by some external interferences^{[11, 12]}. As a kind of uncertain diagnosis, probabilistic fault diagnosis only requires the task to be completed correctly with a high probability, which greatly reduces the cost. Therefore, it is worth exploring the fault diagnosis of large-scale multiprocessor systems by the probability method.

Table  1.  PMC Model

Tester a	Testee b	$\delta(a, b)$
Fault-free	Fault-free	0
Fault-free	Faulty	1
Faulty	Fault-free	0 or 1
Faulty	Faulty	0 or 1
Note: The state of a node is “fault-free” means that this node can work normally, whereas that the state of a node is “faulty” means that this node cannot work normally.

下载: 导出CSV 

| 显示表格

Probabilistic fault diagnosis has attracted extensive attention because of its small costs and real-time performance. Blough et al.^[13] proposed a probabilistic approach, which shows that each node can be correctly diagnosed when the test time of each node is slightly longer than the linear test time. Fussell and Rangarajan^[14] presented a corresponding probabilistic diagnosis algorithm. Subsequently, Tang and Song^[15] put forward the diagnosis algorithm based on a voting scheme, and proved that this diagnosis strategy can detect nearly all nodes, where the threshold $k=1$ and the network scale $n\rightarrow \infty$. Rangarajan and Fussell^[16] gave a new hierarchical algorithm for $k=1$. Note that the threshold $k$ is a central parameter to determine whether there are faulty clusters in a multiprocessor system, which reflects the size of a faction. A faction is defined as a connected subgraph with consistent syndrome. The larger the threshold $k$, the more likely all nodes in the faction are to be fault-free. The diagnosis algorithm with $k=2$ to diagnose the state of the node cluster in simple rectangular grid was provided by Huang et al.^[17]. Tang et al.^[18] studied the probabilistic fault diagnosis of a regular topology in which any pair of adjacent nodes do not have common neighbors for $k=2$. On this basis, Lu et al.^[19] further elaborated on the problem of probabilistic diagnosis of arbitrary topologies with shared nodes. Lately, the probabilistic diagnosis of clustered faults of hypercube for $k=3$ was explored by Lv et al.^[20]. Motivated by this, we further consider general regular graphs with the girth of at least 6, which contain a large class of networks, such as star graphs^[21], pancake networks^[22], and burning pancake networks^[23]. On the one hand, we establish a diagnosis algorithm with the linear time complexity, which extends the threshold proposed in [18] from $k\leqslant 2$ to $k=3$. On the other hand, this paper focuses on the probabilistic fault diagnosis of the $d$-regular and $d$-connected graph, which is an improvement on [20]. More specifically, we give the probabilities that all nodes of the $d$-regular and $d$-connected graph can be correctly diagnosed in the continuous state under the Weibull fault distribution and the Chi-square fault distribution. We prove that they approach to 1, which implies that our diagnosis algorithm can correctly diagnose almost all nodes of the graph.

The remainder of the paper is arranged as follows. Some basic notations and definitions are given in Section 2. We then give the diagnosis algorithm of general graphs in Section 3. Afterwards, Section 4 and Section 5 analyze the performance of the local and global fault distributions of general regular graphs, respectively. Section 6 summarizes the study.

2.   Preliminaries

A multiprocessor system can be denoted as a simple and undirected graph $G=(V, E)$, where $V$ denotes the set of nodes and $E$ denotes the set of edges in $G$. The graph consists of $|V|$ processors that are homogenous to one another, where every node $a\in V$ indicates a processor, and every edge $(a, b)\in E$ indicates a physical link between $a$ and $b$. The neighborhood $N(a)$ of any node $a$ is defined as the set of all nodes adjacent to $a$. The size of $N(a)$ is expressed as the degree of node $a$, that is, $d(a)=|N(a)|$. The maximum degree is represented by $\Delta= \max \{d(a)$ $|\ a\in V\}$. The open neighbor of the node subset $S$ is denoted by $N(S)=\{b\in V-S\ | \ a\in V(S)$ and $(a, b)\in E\}$. The closed neighbor of $S$ is denoted by $N[S]=N(S)\cup S$. The subgraph induced by $S$ of $G$, denoted by $G[S]$, is the graph with the node set $S$ and the edge set $\{(a, b)\ |\ a, b\in V(S)$ and $(a, b)\in E\}$. The girth of the graph $G$ is the smallest cycle length, denoted by $g(G)$. The test result between any two nodes $a$ and $b$ is called syndrome of edge $(a, b)$, which is represented by $\delta(a, b)\in\{0,1\}$. In the PMC model, if the tester $a$ is a fault-free node, $\delta(a, b)=0$ represents that node $b$ is diagnosed as a fault-free node, and $\delta(a, b)=1$ represents that node $b$ is diagnosed as a faulty node. If the tester $a$ is a faulty node, then $\delta(a, b)=0$ or $\delta(a, b)=1$, which represents that node $b$ is diagnosed as a fault-free node or a faulty node, as shown in Table 1. For convenience, we let $\Gamma(a)=\left\{b\in N(a)|\delta(a, b) = 0 \right\}$.

In probabilistic fault diagnosis, the fault-free node $a$ is denoted by $a^{+}$, the faulty node $a$ is denoted by $a^{-}$, and the suspicious node $a$ is denoted by $a^{0}$. We assume that each node has the same fault-free probability $p$, and the nodes are independent for each other, no matter whether they are fault-free or not. The probability that node $a$ is fault-free is recorded as $P_{a^{+}}$, and the probability that node $a$ is faulty is recorded as $P_{a^{-}}$. Thus, $P_{a^{+}}=p$ and $P_{a^{-}}= 1- P_{a^{+}}= 1-p$. If $\delta(a, b)=0$ (resp., 1), then $a$ is matched to $b$ (resp., $a$ is not matched to $b$). $P_{\delta(a,\ b)}$ represents the probability of edge $(a, b)$, indicating whether node $a$ is matched to node $b$ or not. $P_{c}(a)$ (resp., $P_{w}(a)$) indicates the probability that the node $a$ is correctly (resp., wrongly) diagnosed. Next, we will introduce several prior probabilities and give the probabilistic PMC model, as shown in Table 2.

Table  2.  Probabilistic PMC Model

Tester a	Testee b	$\delta(a, b)$
Fault-free	Fault-free	0 $(P_{\delta(a^{+},\ b^{+})}=1)$
Fault-free	Faulty	0 $(P_{\delta(a^{+}, \ b^{-})} = 1 - \gamma)$
		or
		1 $(P_{\delta( a^{+},\ b^{-} )}=\gamma)$
Faulty	Fault-free	0 $(P_{\delta(a^{-},\ b^{+})} = 1 - \gamma)$
		or
		1 $(P_{\delta(a^{-},\ b^{+})}=\gamma)$
Faulty	Faulty	0 $(P_{\delta(a^{-},\ b^{-})} = \beta)$
		or
		1 $(P_{\delta(a^{-},\ b^{-})} = 1 - \beta)$
Note: The state of a node is “fault-free” means that thisnode can work normally, whereas that the state of a node is“faulty” means that this node cannot work normally.

下载: 导出CSV 

| 显示表格

For $a^{+}$ and $b^{+}$, we suppose

For $a^{+}$ and $b^{-}$ (or, $a^{-}$ and $b^{+}$), we suppose

For $a^{-}$ and $b^{-}$, we suppose

In fact, with the increasing number of nodes, $\beta$ approaches to 0 and $\gamma$ approaches to 1.

3.   Local Fault Diagnosis Algorithm of General Graphs

In this section, we propose a new local diagnosis algorithm for general graphs with girth no less than 6, which improves the algorithms in [17, 18].

Huang et al.^[17] presented a local fault diagnosis algorithm with the threshold $k=2$, which claims that all nodes in a connected subgraph are regarded as fault-free nodes while the other nodes are regarded as faulty nodes.

Definition 1^[17]. For a simple and undirected graph $G=(V, E)$ and $S\subseteq V$, $S$ forms a faction if it satisfies the following three conditions.

1) $G[S]$ is a connected subgraph.

2) For every edge $(a, b)\in G[S]$, $\delta(a, b)=0$.

3) For every node $a\in S$ and every node $b\in N(a)$ $-S$, $\delta(a, b)=1$.

Claim 1^[17]. Every fault-free node (or, faulty node) is always in a faction.

In fact, we can measure the state of nodes in a faction by the threshold $k$. If the size of a faction exceeds $k$, then every node in the faction is fault-free, that is to say, the faction is deemed as a really fault-free component (i.e., the component in which all the nodes are fault-free); otherwise the faction is a faulty component (i.e., the component in which there exists at least one faulty node). Clearly, for any suspicious node $a$, if $a$ belongs to a faction whose size is more than $k$, then $a$ is diagnosed as a fault-free node. Hence, we propose Algorithm 1 to diagnose the states of the local nodes in $G$ for $k=3$, and we further give the correctness proof and time complexity of Algorithm 1 by Theorem 1.

Theorem 1. Any suspicious node $a$ is diagnosed as a faulty node by Algorithm 1 if and only if node $a$ belongs to a faction whose number of nodes is no more than 3, and the time complexity of Algorithm 1 is $O(\Delta)$, where $\Delta$ is the maximum degree of $G$.

Proof. Necessity. Suppose that node $a$ is in the faction whose number of nodes is greater than 3. Then, node $a$ satisfies one of the following cases: node $a$ has at least three matching neighbors in the faction, or node $a$ has two matching neighbors, one of which has another matching neighbor except $a$, or node a has just one matching neighbor, which has at most two matching neighbors except $a$ in the faction. This implies that node $a$ must meet any one of the four cases in Fig.1. Thus, $a$ will be diagnosed as a fault-free node through lines 3–34 of Algorithm 1.

Figure  1.  Four cases in which node a is diagnosed as a fault-free node for k > 3. (a) a has more than three matching neighbors. (b) a has two matching neighbors. (c) a has exactly one matching neighbor, which has at least three matching neighbors. (d) a has exactly one matching neighbor, which has two matching neighbors.

下载: 全尺寸图片 幻灯片

Sufficiency. If node $a$ belongs to a faction whose number of nodes is less than or equal to 3, then $|\Gamma(a)|\leqslant2$. In other words, node $a$ has at most two matching neighbors in the same faction, say $a_{1}$ and $a_{2}$. Since $a_{1}$ and $a_{2}$ are the merely two neighbors in the faction, they cannot be diagnosed by line 9 in Algorithm 1. If node $a$ has exactly one matching neighbor $a_{1}$ for $k\leqslant 2$, there are at most three nodes $a$, $a_{1}$ and $b_{1}$ in the same faction, which cannot be diagnosed by line 17 and line 22 in Algorithm 1. As a result, the above conditions do not meet any case in Fig.1. In addition, if node $a$ does not have a matching neighbor, it is diagnosed as a faulty node by line 36 in Algorithm 1. Therefore, $a$ is diagnosed as faulty.

In the following, we analyze the time complexity of Algorithm 1.

If node $a$ is a suspicious node in graph $G$, we can conduct diagnosis according to the faction with $k=3$. To be exact, the time complexity mainly depends on the execution of Algorithm 1 (lines 14–29). In lines 14, 16, 19, and 21, all neighbors of node $a$ in $G$ are diagnosed and the number of tests is at most $\Delta(G)$. Thus, the time complexity of these lines (lines 14, 16, 19, and 21) is at most $O(\Delta)$. The time complexity of the remaining steps is $O(1)$. Therefore, the total time complexity of Algorithm 1 is $O(\Delta)$. □

In summary, Algorithm 1 adopts the breadth first search strategy, and its main idea is to introduce a threshold $k$ to quantify the reliability of faction. If the size of a faction is greater than or equal to $k$, then all nodes in this faction are truly fault-free nodes; otherwise, all nodes are considered to be faulty nodes. Based on Claim 1 and Theorem 1, determining the state of a node only requires considering the size of the faction in which the node is located. In fact, it is enough to diagnose a node and its neighbors for general graphs with girth no less than 6 (in other words, the number of common nodes between any two non-adjacent nodes in the faction is at most 1) by Algorithm 1.

4.   Local Performance Analysis of General Regular Graphs

In this section, we will supply the local fault diagnosis of the $d$-regular and $d$-connected graph ${\cal{G}}$ ($d$ is a positive integer) and afford the probability that any node is correctly diagnosed, provided that the threshold does not exceed 3. Recalling the previous notations, $P_{a^{+}}=p$ (resp., $P_{a^{-}}=1-p$), where $P_{a^{+}}$ (resp., $P_{a^{-}}$) is the probability that $a$ is a fault-free node (resp., a faulty node). Let $P_{c}(a^{+})$ (resp., $P_{c}(a^{-})$) be the probability that $a^{+}$ (resp., $a^{-}$) is correctly diagnosed and $P_{w}(a^{+})$ (resp., $P_{w}(a^{-})$) be the probability that $a^{+}$ (resp., $a^{-}$) is wrongly diagnosed, where $a$ is a node of ${\cal{G}}$.

Note that $P_{c}(a^{+})=1-P_{w}(a^{+})$. If we want to calculate the probability that the fault-free node $a$ is correctly diagnosed, the key is to compute $P_{w}(a^{+})$. According to the properties of ${\cal{G}}$ and Algorithm 1, if $a$ is a fault-free node, we can list eight cases such that $a$ is diagnosed as a faulty node, provided that node $a$ belongs to a faction with $k\leqslant 2$. This implies that $P_{w}(a^{+})=\sum\nolimits^{8}_{i=1}P_{w}^{i}(a^{+})$, where $P_{w}^{i}(a^{+})$ denotes the probability of the local state-syndrome pattern such that $a$ is diagnosed as a faulty node. Furthermore, we introduce the following symbols: $N_{{\cal{G}}}(a)=\{a_1, a_2, \ldots, a_{d}\}$, $N_{{\cal{G}}}(a_{i})=\{b_1, b_2, \ldots, b_{i-1}, a, b_{i+1}, \ldots, b_{d}\}$, $L = \left\{1, \right.$ $\left. 2,\ldots d\right\}= \langle d\rangle, \ M=\langle d\rangle \setminus \{i\},\ N=\langle d\rangle \setminus \{j\},\ K=\langle d\rangle \setminus \{i,\, j\}$, and $P_{a_{K}}=\prod\limits_{k\in K}P_{a_{k}}.$

In what follows, we will determine the probability that node $a$ is wrongly diagnosed by calculating $P^{1}_{w}(a^{+}),P^{2}_{w}(a^{+}),\ldots$, and $P^{8}_{w}(a^{+})$, respectively.

Lemma 1. $P^{1}_{w}(a^{+})=(1-p)^{d}\gamma^{d}.$

Proof. In the local-syndrome pattern of case 1 (see Fig.2(a)), $a^{+}$ is surrounded by $d$ mismatching faulty neighbors $a^{-}_{1}, a^{-}_{2}, \ldots, a^{-}_{d}$.

Figure  2.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 1. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 1.

下载: 全尺寸图片 幻灯片

Hence, we have

for any $i\in L=\{1,2,\ldots, d\}$.

Thus,

Then, the probability of occurrence for case 1 is

Lemma 2. $P^{2}_{w}(a^{+})=dp(1-p)^{2d-2}\gamma^{2d-2}.$

Proof. In the local-syndrome pattern of case 2 (see Fig.3(a)), node $a^{+}$ is surrounded by $d-1$ mismatching faulty neighbors except $a_i^{+}$.

Figure  3.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 2. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 2.

下载: 全尺寸图片 幻灯片

By Lemma 1, it is easy to see

Since $a_i$ has $d$ choices, the probability of occurrence for this fault pattern is

Lemma 3. $P^{3}_{w}(a^{+})=d(1-\gamma)\gamma^{d-1}\theta^{d-1}(1-p)^{d}$.

Proof. In the local-syndrome pattern of case 3 (see Fig.4(a)), the node $a^{+}$ is surrounded by $d-1$ mismatching faulty neighbors except $a_i^{-}$.

Figure  4.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 3. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 3.

下载: 全尺寸图片 幻灯片

Clearly, $P_{a^{-}_M}P_{\delta(a^{+},\ a^{-}_M)}=(1-p)^{d-1}\gamma^{d-1}.$ In addition, for any suspicious node $b^{0}_j\in b^{0}_M$, since $b_j^{+}$ and $b_j^{-}$ are independent, we have

Letting $\theta=p\gamma+(1-p)(1-\beta)$, we have

By the arbitrariness of $a_i$, the probability of occurrence for this fault pattern is

Lemma 4. $P^{4}_{w}(a^{+})=d(d-1)p(1-p)^{2d-2} \gamma^{2d-3} \times$ $\left(p (1-p)^{d-2} \gamma^{d-1}+ \theta^{d-1}(1-\gamma)\right)$.

Proof. For the local-syndrome pattern of case 4 (see Fig.5(a)), we first need to discuss the probability of $b_{i}$ in different situations.

Figure  5.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 4. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 4.

下载: 全尺寸图片 幻灯片

If $b_{i}$ is a fault-free node, then the nodes surrounding it are faulty nodes except $a_{i}$. The probability that $b^{+}_{i}$ is surrounded by $d-1$ mismatching faulty neighbors is

If $b_{i}$ is a faulty node, then the nodes surrounding it are suspicious nodes except $a_{i}$. The probability that $b^{-}_{i}$ is surrounded by $d-1$ mismatching suspicious neighbors is

Therefore,

Next, since the node $a_{i}$ is surrounded by $d-2$ mismatching faulty nodes except $a^{+}$ and $b_{i}^{0}$, we have

Then, we compute the probability of the fault-free node $a$ being misdiagnosed. Since node $a$ is surrounded by one matching fault-free node $a_{i}$ and $d-1$ mismatching faulty nodes, we have

Owing to the arbitrariness of choosing $a_{i}$ and $b_{i}$, we have $P^{4}_{w}(a^{+})=d(d-1)p(1-p)^{2d-2}\gamma^{2d-3}\left(p(1-\right.$ $\left.p)^{d-2}\right.{\gamma^{d-1}}+\theta^{d-1}(1-\gamma)).$ □

Lemma 5. $P^{5}_{w}(a^{+})=d(d-1) (1-\gamma) \gamma^{d-1} \theta^{d-2}\left(1- \right.$$\left. p\right)^{d+1} (p(1-p)^{d-2} (1-\gamma)\gamma^{d-1}+\theta^{d-1}\beta).$

Proof. In the local-syndrome pattern of case 5 (see Fig.6(a)), by Lemma 4, we have

Figure  6.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 5. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 5.

下载: 全尺寸图片 幻灯片

Because node $a_{i}$ is surrounded by $d-2$ mismatching suspicious nodes except $a^{+}$ and $b_{i}^{0}$,

Since node $a$ is surrounded by one matching faulty node $a_{i}$ and $d-1$ mismatching neighbors, we have

Furthermore, we have

Lemma 6. $P^{6}_{w}(a^{+})=\binom{d}{2}p^{2}(1-p)^{3d-4}\gamma^{3d-4}.$

Proof. In the local-syndrome pattern of case 6 (see Fig.7(a)), $a^{+}$ has two matching fault-free neighbors, say $a_i^{+}$ and $a_j^{+}$. Let the neighbors of $a^{+}, a_i^{+}$, and $a_j^{+}$ be denoted by $a_K^{-}, b_M^{-}$, and $c_N^{-}$, respectively.

Figure  7.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 6. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 6.

下载: 全尺寸图片 幻灯片

Clearly,

By Lemma 2, we have

Due to the arbitrariness of $a_i$ and $a_j$, we have

Lemma 7. $P^{7}_{w}(a^{+} ) = \binom{d}{2}p\theta^{d-1}\gamma^{2d - 3}(1 - \gamma)(1 - p)^{2d-2}.$

Proof. In the local-syndrome pattern of case 7 (see Fig.8(a)), $a^{+}$ has one matching fault-free neighbor $a_i^{+}$, and one matching faulty neighbor $a_j^{-}$. The neighbor nodes of $a^{+}$ and $a_i^{+}$ are $a_K^{-}$ and $b_M^{-}$ respectively, while the neighbors of $a_j^{-}$ are diagnosed as suspicious nodes (fault-free or not), denoted by $c_N^{0}$.

Figure  8.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 7. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 7.

下载: 全尺寸图片 幻灯片

By Lemma 3 and Lemma 6, it is easy to see

Note that

By the arbitrariness of choosing $a_i$ and $a_j$, the probability of occurrence for this fault pattern is

Lemma 8. $P^{8}_{w}(a^{+}) = \binom{d}{2}\gamma^{d-2}(1 - \gamma)^{2}(1 - p)^{d}\theta^{2d-2}$.

Proof. In the local-syndrome pattern of case 8 (see Fig.9(a)), $a^{+}$ has two matching faulty neighbors, say $a_i^{-}$ and $a_j^{-}$.

Figure  9.  (a) $a^{+}$ is wrongly diagnosed in the local-syndrome pattern of case 8. (b) $a^{-}$ is correctly diagnosed in the local-syndrome pattern of case 8.

下载: 全尺寸图片 幻灯片

By Lemma 7, it is easy to see

Moreover,

By the arbitrariness of choosing $a_i$ and $a_j$, the probability of occurrence for this fault pattern is

According to the fact that $P_{c}(a^{+})=1-\{P^{1}_{w}(a^{+})+ P^{2}_{w}(a^{+})+...+P^{8}_{w}(a^{+})\}$, by Lemmas 1–8, we derive the following theorem.

Theorem 2. For any node $a\in V({\cal{G}})$, the probability that the fault-free node $a$ is correctly diagnosed is

where $\theta=p\gamma+(1-p)(1-\beta)$.

Based on the above discussions, similarly, we list Table 3 to analyze the probabilities $P^{i}_{c}(a^{-})\ (i\in\langle 8\rangle)$ that the faulty node $a$ is correctly diagnosed.

Table  3.  Probability of 8 Cases in Which Faulty Node a Is Correctly Diagnosed

Local State-Syndrome Pattern	Probability of Correct Identification of Faulty Node $a$
Fig.2(b)	$\theta^{d}$
Fig.3(b)	$d(1-\gamma)\gamma^{d - 1}p(1-p)^{d - 1}\theta^{d - 1}$
Fig.4(b)	$d(1-p)\beta\theta^{2d-2}$
Fig.5(b)	$d(d - 1)p(1 - p)^{d - 1}(1 - \gamma)\gamma^{d - 2}\theta^{d - 1}(p (1 - p)^{d - 2}\gamma^{d - 1}+$
	$(1 - \gamma)\theta^{d - 1})$
Fig.6(b)	$d(d - 1)(1 - p)^{2}\beta\theta^{2d - 3}(p(1 - \gamma)\times$
	$(1 - p)^{d - 2}\gamma^{d - 1}+\theta^{d - 1})$
Fig.7(b)	$\binom{d}{2}(1-\gamma)^{2}p^{2}(\gamma(1-p))^{2d - 2}\theta^{d - 2}$
Fig.8(b)	$\binom{d}{2}\beta\gamma^{d - 1}(1-\gamma)p(1-p)^{d}\theta^{2d - 3}$
Fig.9(b)	$\binom{d}{2}{\beta}^{2}(1-p)^{2}\theta^{3d-4}$

下载: 导出CSV 

| 显示表格

Note that $P_{c}(a^{-})=\sum\nolimits^{8}_{i=1}P^{i}_{c}(a^{-})$. Then, we derive the following theorem.

Theorem 3. For any node $a\in V({\cal{G}})$, the probability that the faulty node $a$ is correctly diagnosed is

where $\theta=p\gamma+(1-p)(1-\beta)$.

According to Theorem 2 and Theorem 3, we obtain the probability that any node in ${\cal{G}}$ is correctly diagnosed.

5.   Global Performance Analysis of General Regular Graphs

In this section, we present the global performance analysis of ${\cal{G}}$ in the continuous state through the Laplace transform and two fault distributions. That is, we need to show that $Y_{c}/Y$ approaches to 1 and $F_{c}/F$ approaches to 1, where $Y$ (resp., $F$) is the mathematical expectation of the probability of nodes diagnosed to be fault-free (resp., faulty), and $Y_{c}$ (resp., $F_{c}$) is the mathematical expectation of the probability that the fault-free (resp., faulty) nodes can be correctly diagnosed. In other words, all nodes can be correctly diagnosed with a high probability in ${\cal{G}}$.

Suppose that $p$ is a random variable that can be expressed as $p={\rm{e}}^{-m}$. Then

where $E(p)$ is the mathematical expectation of $p$, and $f(m)$ is the probability density function of $m$.

Since $m$ is also a random variable, we utilize the Laplace transform (denoted as $L(s)$) of $m$ to perform the probabilistic diagnosis of clustered faults. To be exact, for any $s\geqslant 0$,

Clearly, $Y=L(1)$ and $Y=1-F$. To obtain the value of $Y_c/Y$ and $F_c/F$, we need to prove that $P_c(a^{+})$ and $P_c(a^{-})$ are polynomials with respect to $p$. Thus, we derive Lemma 9 ¹ and Theorem 4.

Lemma 9. Given any node $a\in V({\cal{G}})$, the probability that $a$ is correctly diagnosed is

1) $P_{c}(a^{+})=1+\displaystyle\sum\limits^{3d-2}_{i=0}w_{i}p^{i}$,

2) $P_c(a^{-})=\displaystyle\sum\limits^{3d-2}_{i=0}\hat{w}_{i}p^{i}$.

Theorem 4. The mathematical expectation expressions $Y_{c}/Y$ and $F_{c}/F$ are determined as follows.

1) $Y_{c}/Y=(L(1)+\displaystyle\sum\limits^{3d-2}_{i=0}w_{i}L(i+1))/L(1);$

2) $F_{c}/F = (\hat{w}_{0} + \displaystyle\sum\limits^{3d-2}_{i=1}(\hat{w}_{i} - \hat{w}_{i-1})L(i) - \hat{w}_{3d - 2}L(3d - 1))/ (1-L(1))$.

Proof. 1) Clearly, $Y=L(1), F=1-L(1)$. By Lemma 9, the mathematical expectation of fault-free nodes diagnosed correctly is

2) The mathematical expectation of faulty nodes diagnosed correctly is

where $w_{i}$ and $\hat{w}_{i}$ are two parameters in Lemma 9. □

By the results mentioned above, we discover that the Laplace transform $L(s)$, which is determined by the distribution of random variable $m$, plays an important role in the global performance analysis. Both the Weibull fault distribution and the Chi-square fault distribution are extensively utilized in fault diagnosis. In the following, we will explore the situations that all nodes in ${\cal{G}}$ can be correctly diagnosed with a high probability under these two fault distributions.

5.1   Weibull Fault Distribution

Here, we investigate the probability that the nodes in ${\cal{G}}$ are correctly diagnosed under the Weibull fault distribution.

Let $m(\geqslant0)$ be a random variable to obey the Weibull fault distribution, and then its probability density function is

where $\lambda>0$ is a scale parameter and $\xi>0$ is a shape parameter.

For convenience, let $\mu=m^{\xi-1}/\lambda^{\xi}$. Then, the probability density function is $f(m)=\xi\mu{\rm{e}}^{-m\mu}.$ The Laplace transform of $m$ under the Weibull distribution is

Hence,

Combining the above four formulas with Theorem 4, we obtain the following lemma.

Lemma 10. The mathematical expressions $Y_{c}/Y$ and $F_{c}/F$ under the Weibull distribution are determined as follows.

1) $Y_{c}/Y=1+\displaystyle\sum\limits^{3d-2}_{i=0}w_{i}\dfrac{\mu+1}{\mu+i+1};$

2) $\begin{array}{l} F_{c}/F = \dfrac{(1 - \xi)\mu + 1}{1 + \mu} \left( \hat{w}_{0} + \displaystyle\sum\limits^{3d-2}_{i=1}(\hat{w}_{i} - \hat{w}_{i+1})\dfrac{\xi\mu}{\mu+i}- \right.\end{array}$$\qquad \qquad\quad \qquad \left. \hat{w}_{3d-2}\dfrac{\xi\mu}{\mu+3d-1}\right)$.

Next, we need to show that the states of nodes in ${\cal{G}}$ can be correctly diagnosed with a high probability. That is, $Y_{c}/Y\rightarrow 1$ and $F_{c}/F\rightarrow 1$ when $\xi\rightarrow 0, \hat{w}_{0}\rightarrow 1$ and $d\rightarrow \infty$.

Theorem 5. If $k\rightarrow 0, \hat{w}_{0}\rightarrow 1$ and $d\rightarrow \infty$, then $Y_{c}/Y\rightarrow 1$ and $F_{c}/F\rightarrow 1$.

Proof. By Lemma 10, it is easy to verify that

for $\xi\rightarrow 0, \hat{w}_{0}\rightarrow 1$ and $d\rightarrow \infty$. Thus,

Therefore, the diagnostic strategy can identify almost all nodes in ${\cal{G}}$ successfully under the Weibull fault distribution.

5.2   Chi-square Fault Distribution

In the following, we discuss the probability that the nodes in ${\cal{G}}$ are correctly diagnosed under the Chi-square fault distribution.

Let $x(\geqslant0)$ be a random variable to obey the Chi-square fault distribution. Then, its probability density function is

where $\zeta$ is a constant.

For convenience, let $\sigma=\zeta/2$. Since the Chi-square fault distribution is a special case of the Gamma fault distribution, the mean of $x$ is $\lambda=2\sigma$. Hence, the Laplace transform of $x$ under the Chi-square fault distribution is

Thus,

By Theorem 4, we have the following lemma.

Lemma 11. The mathematical expectation expressions $Y_c/Y$ and $F_c/F$ under the Chi-square fault distribution are determined as follows.

1) $Y_{c}/Y=1+\displaystyle\sum\limits^{3d-2}_{i=0}w_{i}\left(\dfrac{1+\lambda/\sigma}{1+(i+1)\lambda/\sigma}\right)^{-\sigma}$;

2) $F_{c}/F = \dfrac{1}{1-(1+\lambda/\sigma)^{-\sigma}}\bigg(\hat{w}_{0} + \displaystyle\sum\limits^{3d-2}_{i=1}(\hat{w}_{i} - \hat{w}_{i+1})\times \Bigg.\qquad\quad\qquad\qquad\ (1+ i\lambda/\sigma)^{-\sigma}-\hat{w}_{3d-2}(1+(3d-1)\times \qquad\quad\qquad\qquad \lambda/\sigma)^{-\sigma}\bigg)$.

Next, we need to show that both $Y_{c}/Y$ and $F_{c}/F$ approach to 1, when $\hat{w}_{0}\rightarrow 1$ and $d\rightarrow \infty$.

Theorem 6. If $\hat{w}_{0}\rightarrow 1$ and $d\rightarrow \infty$, then $Y_{c}/Y\rightarrow 1$ and $F_{c}/F\rightarrow 1$.

Proof. Since $\zeta$ is a constant and $\zeta>0$, when $\hat{w}_{0}\rightarrow 1$, by Lemma 11, it is easy to see that

Since $\sigma=\zeta/2$, $\lambda=2\sigma$, we have

The monotonicity of the above function with respect to $i$ implies

Hence,

Owing to the monotonicity of the function, we have

Hence, when $\hat{w}_{0}\rightarrow 1$ and $d\rightarrow \infty$, we have

In summary, the diagnostic strategy can identify almost all nodes of general regular graphs successfully under the Chi-square fault distribution.

6.   Conclusions

In this paper, we derived the following conclusions and results.

$1)$ We proposed a local diagnosis algorithm with linear time complexity for general graphs and analyzed its effectiveness.

$2)$ Based on the algorithm, we computed the probability of correctly diagnosing any node in a $d$-regular and $d$-connected graph under the probabilistic PMC (Preparata Metze Chien) model. Our calculations indicate that the algorithm efficiently performs node diagnosis in this probabilistic model.

$3)$ We investigated the scenarios in which all nodes in a $d$-regular and $d$-connected graph can be correctly diagnosed with a high probability under Weibull and Chi-square fault distributions. The analysis revealed that the algorithm exhibits excellent diagnostic performance under these fault distributions.

$4)$ The research findings demonstrated that the probabilities of correctly diagnosing all nodes in a $d$-regular and $d$-connected graph approach to 1 in the continuous state under both fault distributions. This implies that the diagnosis algorithm can accurately diagnose almost all graph nodes in practical applications.

In the future, we will try to find a bigger k, which is a central parameter reflecting the size of a faction and determining whether there are faulty clusters in a multiprocessor system. The larger the value of k, the more likely all nodes in the faction are to be fault-free. We aim to use larger k to solve the probabilistic fault diagnosis for general regular networks.