# On Fault Identification in Interconnection Networks under the Comparison Model.

1. IntroductionWith the rapid development of digital technology, multiprocessor computer systems can now contain hundreds and thousands of processors. It is inevitable that some processors in such a system may fail. To ensure reliability, the system should have the ability to identify the faulty processors which can be isolated from the system or replaced by additional fault-free ones. In large multiprocessor computer systems, it is difficult and impractical for each processor to be tested individually by another host. So, it is important and significant to design an effective method of fault diagnosis for such systems in the situation. System-level diagnosis, which is first proposed by Preparata et al. in [1, 2], is an important self-diagnosis strategy. In [1], Preparata et al. introduced the first system-level diagnosis model, called the PMC model, which can be represented by a digraph G = (V, E) and the edge (i, j) means node i tests node j. The test outcome of node i testing node j is represented by [omega](i, j). [omega](i, j) = 1(0) implies that node i judges node j to be faulty (fault-free) and the outcome of test (i, j) is reliable only if node i is fault-free. The PMC model has widely been adopted (see [3-8]). Another practical model is the comparison model (also called MM model), proposed by Maeng and Malek [9, 10]. Sengupta and Dahbura [11] suggested a further modification, called the M[M.sup.*] model, in which any node has to test another two nodes if it is adjacent to them. A comparison model can be represented by an undirected graph G = (V, E). Under the comparison model, node k is a comparator for nodes i and j if and only if (i, k) [member of] E and (j, k) [member of] E. The test outcome of comparator k testing i, j is denoted by [omega](k : i, j). [omega](k : i, j)=1 implies that at least one of the nodes i, j, and k is faulty and [omega](k : i, j)=0 implies that if node k is fault-free, then nodes i and j are all fault-free. The test outcome [omega](k : i, j) is reliable only if node k is fault-free. In other words, if node k is faulty, then [omega](k : i, j) can be arbitrary. It is worth noting that PMC model is a special case of the comparison model [11]. The MM model and the M[M.sup.*] model were adopted in [11-16].

There are two fundamentally different strategies to system-level diagnosis: t-diagnosable [1] and t/t-diagnosable [17]. A system is t-diagnosable if and only if all faulty nodes can be correctly identified in the presence of at most t faulty nodes in this system. And a system is t/t-diagnosable if and only if all faulty nodes can be isolated within a set of sizes at most t in the presence of at most t faulty nodes. Under the PMC model, Hakimi and Amim [18] characterized t-diagnosable systems and [19, 20] characterized t/t-diagnosable systems. Under the comparison model, Sengupta and Dahbura [11] proposed a characterization of t-diagnosable systems. However, the t/t-diagnosable systems have not been as yet characterized under the comparison model. Furthermore, comparing to PMC model, comparison model has a better stability and reliability. And comparing to t-diagnosable systems, t/t-diagnosable systems have an almost 50 percent reduction in the number of the tests. This provides a strong motivation for the study of t/t-diagnosable systems under the comparison model.

In the next section we shall present a characterization of t/t-diagnosable systems under the comparison model. In Section 3 we shall propose some practical properties of AFS's in t/t-diagnosable systems. And in Section 4 we shall use the characterization of t/t-diagnosable systems to figure out the t/t-diagnosability of some special interconnection networks such as n-dimensional hypercube, 2D (3D) mesh, and permutation star graph. In Section 5, simulations and comparisons of the t-diagnosability and the t/t-diagnosability for the interconnection networks are presented. In the last section we draw a conclusion.

2. Characterization of t/t-Diagnosable Systems

Before we present the characterization of t/t-diagnosable systems, we shall do some preliminaries as follows.

Definition 1 (see [11]). Given a system G = (V, E) and a syndrome [sigma], a set X [subset] V is called an allowable fault set (AFS) of the system for [sigma] if, for any three nodes i, j, k [member of] V such that (i, k) [member of] E, (j, k) [member of] E,

(i) if k [member of] V - X and i, j [member of] V - X then [omega] (k: i, j)=0,

(ii) if k [member of] V - X and {i, j} [intersection] X [not equal to] [phi] then [omega](k: i, j)=1.

For a system G = (V, F) and a syndrome <r, let

[[OMEGA].sub.[sigma],t] = |F : F is an AFS of [sigma], [absolute value of F] [less than or equal to] t. (1)

Lemma 2. Given a system G = (V, F) and a syndrome a, with [S.sub.1], [S.sub.2] where [S.sub.1], [S.sub.2] [subset] V are two allowable fault sets for the syndrome [sigma], ([S.sub.1] [union] [S.sub.2]) is also an allowable fault set.

Proof. Let [S.sub.0] = ([S.sub.1] [union] [S.sub.2]) and assume, to the contrary, that [S.sub.0] is not an allowable set. Then, for [S.sub.0], there exist three nodes i, j, k [member of] V such that (i, k) [member of] F, (j, k) [member of] F, and at least one of the conditions of Definition 1 cannot be satisfied.

If condition (i) cannot be satisfied, then there exist three nodes i, j, k [member of] V - [S.sub.0] such that : i, j)=1; thus, [S.sub.1], [S.sub.2] are not allowable fault sets, a contradiction.

Similarly, if condition (ii) cannot be satisfied, then there exists a node k [member of] V - [S.sub.0] and two nodes i, j, {i, j} [intersection] [S.sub.0] [not equal to] 0 such that [omega](k : i, j)=0. It is obvious that if above condition is satisfied, then at least one of [S.sub.1], [S.sub.2] is not an allowable fault set, which is also a contradiction to the hypothesis.

For a system given by G = (V, F) and for a set of nodes X [subset] V, T(X) denotes the set of those nodes in V - X which are compared to some node of X by some node of X: T(X)={j|(i, k) [member of] F, (j, k) [member of] E and i, k [member of] X} - X. For a set of nodes X [subset] V, [G.sub.X] = ([V.sub.X], [E.sub.X]) denotes a graph defined on the set of nodes in V - X - T(X), where = [V.sub.X] - X - T(X) and [E.sub.X]={(i, j)|i, j [member of] [V.sub.X] and [there exists]k [member of] X such that (i, k) [member of] E, (j, k) [member of] E}.

As an example, for the system of Figure 1, if X = {4, 5, 6}, then T(X) = {1, 7} and [V.sub.X] = {2, 3}, [E.sub.X] = {(2, 3)}.

Definition 3. A graph denoted by G = (V, F) is a bipartite graph if there exist two sets P, Q such that P [intersection] Q = [phi], P [union] Q = V and for each edge (i, j) [member of] E, i and j are, respectively, in the two sets(P and Q).

With above preliminaries, we shall state the following theorem. In the following theorem, we use [L.sub.[alpha],[beta]] to denote the set of bipartite graphs with [alpha] and [beta] nodes in the two sets of the bipartition.

Theorem 4. A system with n nodes given by G = (V, F) is t/t-diagnosable if and only if and only if (i) n [greater than or equal to] 2t + 1 and (ii) for each X [subset] V such that [absolute value of X] = n - 2t + p, 0 [less than or equal to] p [less than or equal to] t - 1, [G.sub.X] does not have [L.sub.[alpha],[beta]] with [alpha] + [beta] = 2(t - p) as a node induced subgraph.

Proof.

Necessity. It is obvious that condition (i) must be satisfied; thus we consider condition (ii) now. Suppose that for some X [subset] V such that [absolute value of X] = n - 2t + p, 0 [less than or equal to] p [less than or equal to] t - 1, [G.sub.X] = ([V.sub.X], [E.sub.X]) has [L.sub.[alpha],[beta]] with [alpha] + [beta] = 2(t - p) as a node induced subgraph. Then we have that [absolute value of V - X] = 2t - p, [absolute value of [V.sub.X]] [greater than or equal to] 2(t - p), and [absolute value of T(X)] = [absolute value of V - X - [V.sub.X]] [less than or equal to] p. Let {P, Q} be the bipartition of [L.sub.[alpha],[beta]] such that [absolute value of P] = [alpha], [absolute value of Q] = [beta]. Let Y = V - X - P - Q - T(X); then [absolute value of Y] = p - [absolute value of T(X)]. Let [S.sub.1] = P[union]T(X)[union]Y, [S.sub.2] = Q[union]T(X)[union]Y, then we have that [absolute value of [S.sub.1]] = p + [alpha], [absolute value of [S.sub.2]] = p + [beta] and V - [S.sub.1] - [S.sub.2] = X, [S.sub.1] - [S.sub.2] = P, [S.sub.2] - [S.sub.1] = Q. For the sake of convenience, we make the Venn diagram of the graph G (shown by Figure 2). Note that P [subset] Y - X - T(X); it is easily obtained that for each pair {j, k} [subset] X with (j, k) [member of] F there exists no edge from P to {j, k}. Similarly there exists no edge from Q to {j, k}. On the other hand, since P and Q are the bipartition of [L.sub.[alpha],[beta]], which is a node induced graph of [G.sub.X], any two nodes in P(or Q) are nonadjacent in [G.sub.X]. Hence, no two nodes of P(or Q) are compared by some node of X.

Consider a syndrome [sigma] such that for nodes i, j, k [member of] V with (i, k) [member of] E and (j, k) [member of] E

(i) if i, j, k [member of] X, then [omega](k : i, j)=0;

(ii) if i [member of] [S.sub.1] [union] [S.sub.2], j, k [member of] X, then [omega](k : i, j) =1;

(iii) if i, j [member of] [S.sub.1] [union] [S.sub.2] and k [member of] X, then [omega](k : i, j)=1;

(iv) if i, k [member of] [union] [S.sub.2] and j [member of] X, then if i, k [member of] - [S.sub.2] or i, k [member of] [S.sub.2] - [S.sub.1], then [omega](k : i, j)=0; otherwise [omega](k : i, j)=1;

(v) if i,j,k [member of] [union] [S.sub.2], then if i, j, k [member of] - [S.sub.2] or i, j, k [member of] [S.sub.2]- [S.sub.1], then [omega](k : i, j)=0; otherwise [omega](k : i, j)=1;

(vi) if k [member of] ([S.sub.1] - [S.sub.2]) [union] ([S.sub.2] - [S.sub.1]) and i, j [member of] X, then [omega](k : i, j)=0;

(vii) the other possible test results are arbitrary.

According to Definition 1, it can be easily seen that [S.sub.1] and [S.sub.2] are allowable fault sets for [sigma]. But [absolute value of [S.sub.1] [union] [S.sub.2]] = 2t - p > t, which is a contraction to the assumption that the system is t/t-diagnosable.

Sufficiency. Suppose that the system is not t/t-diagnosable. Then for some syndrome [sigma], we have r [greater than or equal to] 2 distinct allowable fault sets [V.sub.f1], [V.sub.f2], ..., [V.sub.fr] [subset or equal to] V with [absolute value of [V.sub.fi]] [less than or equal to] t such that [absolute value of [[union].sup.r.sub.i=1] [V.sub.fi]] > t. Let k [member of] [1, 2, ..., r} be the minimum integer such that [absolute value of [[union].sup.k-1.sub.i=1] [less than or equal to] t and [absolute value of [[union].sup.k.sub.i=1] = 2t - p > t(0 [less than or equal to] p < t). Let [F.sub.1] = [absolute value of [[union].sup.k-1.sub.i=1] [V.sub.fi] and [V.sub.2] = [V.sub.fk]. By Lemma 2, we can easily get that [F.sub.1] is an allowable fault set. Let [V.sub.c] = [F.sub.1] [intersection] [V.sub.2], V' = [[union].sup.k.sub.i=1][V.sub.fi] - [V.sub.c] = ([F.sub.1] - [F.sub.2]) [union] ([F.sub.2] - [F.sub.1]). By definition of the k, we can easily see that [absolute value of [V.sub.c]] [less than or equal to] p. Let X = V - [[union].sup.k.sub.i=1] [V.sub.fi] = V - ([F.sub.1] [union] [F.sub.2]); then [absolute value of X] = n - 2t + p and T(X) [subset or equal to] [V.sub.c]. Since both of [F.sub.1] and [F.sub.2] are allowable fault sets, ([F.sub.1] - [F.sub.2]) [union] ([F.sub.2] - [F.sub.1]) [subset] [V.sub.X] and [absolute value of ([F.sub.1] - [F.sub.2]) [union] ([F.sub.2] - [F.sub.1])] [greater than or equal to] 2t - p - [V.sub.c] [greater than or equal to] 2(t - p). Note that there always exist two sets P and Q such that P is a subset of ([F.sub.1] - [F.sub.2]) and Q is a subset of ([F.sub.2] - [F.sub.1]) with = 2(t-p). Thus, for any two nodes in P(or Q), they are nonadjacent in [G.sub.X]. It is obvious that {P, Q} are the two parts of the bipartite graph of [G.sub.X] with [absolute value of P] + [absolute value of Q] = 2(t - p), a contradiction. This completes the proof.

Although Theorem 4 gives the characterizations to judge whether a system is t/t-diagnosable or not, it is abstract. Next, we shall present an alternative characterization of t/t-diagnosable systems.

Lemma 5 (see [11]). For any [S.sub.1], [S.sub.2] [subset] V with [S.sub.1] [not equal to] [S.sub.2], ([S.sub.1], [S.sub.2]) is a distinguishable pair if and only if at least one of the following conditions is satisfied:

(1) [there exists]i, k [member of] V - [S.sub.1] - [S.sub.2] and [there exists]j [member of] ([S.sub.1] - [S.sub.2]) [union] ([S.sub.2] - [S.sub.1]) such that (i, k) [member of] E and (j, k) [member of] E,

(2) [there exists]i, j [member of] [S.sub.2] - [S.sub.1] and [there exists]k [member of] V - [S.sub.1] - [S.sub.2] such that (i, k) [member of] E and (j, k) [member of] E, or

(3) [there exists]i, j [member of] [S.sub.1] - [S.sub.2] and [there exists]k [member of] V - [S.sub.1] - [S.sub.2] such that (i, k) [member of] E and (j, k) [member of] E.

It is easily seen that if [S.sub.1], [S.sub.2] are all allowable fault sets for a syndrome [sigma], then ([S.sub.1], [S.sub.2]) is an indistinguishable pair.

Theorem 6. Let G = (V, E) be the undirected graph of a system S with n nodes and n [greater than or equal to] 2t + 1. Then the following statements are equivalent.

(i) S is t/t-diagnosable.

(ii) For any two sets of nodes [S.sub.1], [S.sub.2] [subset or equal to] V with [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]] = t and [S.sub.1] [not equal to] [S.sub.2], at least one of the conditions of Lemma 5 is satisfied.

(iii) For any two sets of nodes [S.sub.1], [S.sub.2] [subset or equal to] V with [absolute value of [S.sub.1]], [absolute value of [S.sub.2]] [less than or equal to] t and [S.sub.1] [subset not equal to] [S.sub.2] and [S.sub.2] [subset not equal to] [S.sub.1], at least one of the conditions of Lemma 5 is satisfied.

Proof.

(i) [??] (ii). Suppose that the system is t/t-diagnosable and, to the contrary, there are two sets of nodes [S.sub.1], [S.sub.2] [subset or equal to] V with [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]] = t and [S.sub.1] [not equal to] [S.sub.2], such that none of the conditions of Lemma 5 can be satisfied. Let X = V - [S.sub.1] - [S.sub.2]; consider a syndrome o such that, for nodes i, j, k [member of] V with (i, k) [member of] E and (j, k) [member of] E,

(1) if i, j, k [member of] X, then [omega](k : i, j)=0;

(2) if i [member of] [S.sub.1] [union] [S.sub.2], j, k [member of] X, then [omega](k : i, j)=1;

(3) if i, j [member of] [S.sub.1] [union] [S.sub.2] and k [member of] X, then [omega](k : i, j)=1;

(4) if i, k [member of] [S.sub.1] [union] [S.sub.2] and j [member of] X, then if i, k [member of] [S.sub.1] - [S.sub.2] or i, k [member of] [S.sub.2] - [S.sub.1], then [omega](k : i, j)=0; otherwise [omega](k : i, j)=1;

(5) if i, j, k [member of] [S.sub.1] [union] [S.sub.2], then if i, j, k [member of] [S.sub.1] - [S.sub.2] or i, j, k [member of] [S.sub.2] - [S.sub.1], then [omega](k : i, j)=0; otherwise [omega](k : i, j)=1;

(6) the other possible test results are arbitrary.

It can observed that [S.sub.1], [S.sub.2] are all allowable fault sets for above syndrome [sigma]. Since [absolute value of ([S.sub.1] [union] [S.sub.2])] > t, the system is not t/t-diagnosable, which is a contradiction.

(ii) [??] (iii). Consider any two sets of nodes [S.sub.1], [S.sub.2] [subset or equal to] V with [absolute value of [S.sub.1]], [absolute value of [S.sub.2]] [less than or equal to] t and [S.sub.1] [subset not equal to] [S.sub.2] and [S.sub.2] [subset not equal to] [S.sub.1]. Without loss of generality, we can assume [absolute value of [S.sub.1]][less than or equal to] [absolute value of [S.sub.2]]. Choose a set of nodes [S.sub.x] [subset or equal to] ([S.sub.2] - [S.sub.1]) such that [absolute value of [S.sub.x]] + [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]]. Choose a set of nodes [S.sub.y] [subset or equal to](V - [S.sub.2] - [S.sub.1]) such that [absolute value of [S.sub.y]] + [absolute value of [S.sub.2]] = t. Let [U.sub.1] = [S.sub.1] [union] [S.sub.x] [union] [S.sub.y] and [U.sub.2] = [S.sub.2] [union] [S.sub.y]. Clearly, [absolute value of [U.sub.1]] = [absolute value of [U.sub.2]] = t and note that

(1) [S.sub.1] - [S.sub.2] = [U.sub.1] - [U.sub.2],

(2) [S.sub.2] - [S.sub.1] [contains or equal to] [U.sub.2] - [U.sub.1],

(3) V - [S.sub.2] - [S.sub.1] [contains or equal to] V - [U.sub.2] - [U.sub.1].

According to the hypothesis, we have that for [U.sub.1] and [U.sub.2] at least one of the conditions of Lemma 5 are satisfied. Therefore, by (1), (2), and (3), for [S.sub.1] and [S.sub.2] at least one of the conditions of Lemma 5 is also satisfied.

(iii) [right arrow] (i). Assume, to the contrary, the system is not t/t-diagnosable. Then for some syndrome a, we have r [greater than or equal to] 2 distinct allowable fault sets [V.sub.f1], [V.sub.f2], ..., [V.sub.fr] [subset not equal to] V with [absolute value of [V.sub.fi]] [less than or equal to] t such that [absolute value of [[union].sup.k-1.sub.i=1] [V.sub.fi]] [less than or equal to] t. Let k [member of] {1, 2, ..., r} be the minimum integer such that [absolute value of [[union].sup.k-1.sub.i=1] [V.sub.fi]] [less than or equal to] t and [absolute value of [[union].sup.k.sub.i=1] [V.sub.fi]] = 2t - p > t(0 [less than or equal to] p < t). Let [F.sub.1] = [[union].sup.k-1.sub.i=1] [V.sub.fi] and [F.sub.2] = [V.sub.fk]. By Lemma 2, we can easily see that [F.sub.1] is an allowable fault set for [sigma]; thus, ([F.sub.1], [F.sub.2]) is an indistinguishable pair. Since [absolute value of [F.sub.1]], [absolute value of [F.sub.2]] [less than or equal to] t and [F.sub.1] [subset not equal to] [F.sub.2] and [F.sub.2] [subset not equal to] [F.sub.1], for [F.sub.1], [F.sub.2] at least one of the conditions of Lemma 5 is satisfied. So, ([F.sub.1], [F.sub.2]) is a distinguishable pair. This is a contradiction.

From the definition of the allowable fault set, we conclude that all faulty nodes must be isolated in union set of all allowable fault sets. In next section, we shall propose some practical properties of t/t-diagnosable system.

3. Properties of t/t-Diagnosable Systems

Theorem 7. For a t/t-diagnosable system G = (V, E) and a syndrome [sigma] in most t faulty nodes situation, if [F.sub.i], [F.sub.j] [member of] [[OMEGA].sub.[sigma],t], then [F.sub.i] [subset or equal to] [F.sub.j] or [F.sub.j] [subset not equal to] [F.sub.i].

Proof. Suppose that, to the contrary, there exist two sets of nodes [F.sub.i], [F.sub.j] [member of] [[OMEGA].sub.[sigma],t] such that [F.sub.i] [subset not equal to] [F.sub.j] and [F.sub.j] [subset not equal to] [F.sub.i], which implies that ([F.sub.i], [F.sub.j]) is an indistinguishable pair. On the other hand, by Theorem 6, for [F.sub.i], [F.sub.j] at least one of the conditions of Lemma 5 is satisfied; thus, ([F.sub.i], Ff) is a distinguishable pair. This is a contradiction.

Theorem 8. For a t/t-diagnosable system G = (V,E) and a syndrome [sigma] in most t faulty nodes situation, if [F.sub.i], [F.sub.j] [member of] [[OMEGA].sub.[sigma],t], then [absolute value of [F.sub.j] - [F.sub.i]] [less than or equal to] 1.

Proof. Suppose that, to the contrary, there exist two sets of nodes [F.sub.i], [F.sub.j] [member of] [[OMEGA].sub.[sigma],t] such that such that [absolute value of [F.sub.j] - [F.sub.i]] [greater than or equal to] 2. It follows from Theorem 6 that [F.sub.j] [??] [F.sub.i] and [absolute value of [F.sub.j]] - [absolute value of [F.sub.i]] = [absolute value of [F.sub.j] - [F.sub.i]] [greater than or equal to] 2. Let [absolute value of [F.sub.j]] - [absolute value of [F.sub.i]] = [absolute value of [F.sub.j] - [F.sub.i]] = 2q + r, where q [greater than or equal to] 1 is an integer and r = 0 or 1. So, [absolute value of [F.sub.i]] = [absolute value of [F.sub.i]] - 2q - r. Let [F'.sub.j] [subset or equal to] ([F.sub.j] - [F.sub.i]) be the subset of [F.sub.j] - [F.sub.i] such that [absolute value of [F.sub.j]] = 2q = 2(t - p), where [t/2] - 1 [less than or equal to] p [less than or equal to] t - 1. Let R be the subset of V - [F.sub.j] such that [absolute value of [F.sub.j]] + [absolute value of R] = 2t - p. Let [S.sub.sub] = [F.sub.j] - [F.sub.i] - [F'.sub.j]. Partition [F'.sub.j] into two parts P and Q such that [absolute value of Q] = [absolute value of P] = t - p. Let [S.sub.1] = P [union] [S.sub.sub] [union] [F.sub.i] [union] R and [S.sub.2] = Q [union] [S.sub.sub] [union] [F.sub.i] [union] R. Note that [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]] = 2t - p - (t - p) = t, [S.sub.1] - [S.sub.2] = P, and [S.sub.2] - [S.sub.1] = Q. Since [S.sub.1] [not equal to] [S.sub.2], for [S.sub.1] and [S.sub.2], at least one of the conditions of Lemma 5 is satisfied. It is easily seen that, for [S.sub.1] and [S.sub.2], if any one condition of Lemma 5 is satisfied, then [F.sub.j] and [F.sub.i] cannot be AFS at the same time, a contradiction.

Theorem 9. If S is a t/t-diagnosable system with f faulty nodes (1 [less than or equal to] f [less than or equal to] t), given any syndrome a, then each of the following conditions must hold:

(i) 1 [less than or equal to] [absolute value of [[OMEGA].sub.[sigma],t]] [less than or equal to] 2.

(ii) If [[OMEGA].sub.[sigma],t] = {[F.sub.i], [F.sub.j]} where [F.sub.i] [not equal to] [F.sub.i], then either [F.sub.i] [subset] [F.sub.j] with [absolute value of [F.sub.j] - [F.sub.i]] = 1 or [F.sub.j] [subset] [F.sub.i] with [absolute value of [F.sub.i] - [F.sub.j]] = 1.

Proof. Since the set of all faulty nodes is ASF, we have that 1 [less than or equal to] [absolute value of [[OMEGA].sub.[sigma],t]]. Subsequently, we will prove [absolute value of [[OMEGA].sub.[sigma],t]] [less than or equal to] 2. Assume, to the contrary, that [absolute value of [[OMEGA].sub.[sigma],t]] [greater than or equal to] 3. Then, by Theorem 7, there exist at least three distinct AFS [F.sub.1], [F.sub.2], [F.sub.3] [member of] [[OMEGA].sub.[sigma],t] such that [F.sub.1] [subset] [F.sub.2] [subset] [F.sub.3]. Therefore, [absolute value of ([F.sub.3] - [F.sub.1])] [greater than or equal to] 2, which is a contradiction to Theorem 8.

Theorems 7 and 8 imply that condition (ii) is true.

With the above characterizations and properties of the t/t-diagnosable system, we are able to judge whether an interconnection network is a t/t-diagnosable system or not. In next section, for some practical interconnection networks such as n-dimensional hypercube, 2D (3D) mesh, and permutation star graph, we shall find out a maximum value of t such that these interconnection networks are t/t-diagnosable systems.

4. Application

In fact, for a given value of t, using Theorems 4 and 6 to verify whether a system is t/t-diagnosable or not is very complicated. Now, we will propose a simple sufficient condition and a simple necessary condition to test whether a system is t/t-diagnosable.

A system is given by G = (V, E). For a node i [member of] V, let N(i) = {j|(i, j) [member of] E and j [not equal to] i}; for a set of nodes X [subset] V, let N(X) = [[union].sub.i[member of]X] N(i) - X.

Theorem 10. Let G=(V,E) be the undirected graph of a system 5. If S is a t/t-diagnosable system, then [absolute value of N({i, j})] [greater than or equal to] t for each pair of nodes {i, j} [subset] V.

Proof. Assume that the system is t/t-diagnosable and there is one pair of nodes {i, j} such that [absolute value of N({i, j})] < t. Let [S.sub.1] = N({i, j}) [union] {i} and [S.sub.2] = N({i, j) [union] {j}. Note that [absolute value of [S.sub.1]] [less than or equal to] t, [absolute value of [S.sub.2]] [less than or equal to] t and [S.sub.1] - [S.sub.2] = {i}, [S.sub.2] - [S.sub.1] = {j}. Then for [S.sub.1], [S.sub.2], none of the conditions of Lemma 5 is satisfied, which is a contradiction to Theorem 6.

Theorem 11. Let G = (V, E) be the undirected graph of a system S. If [absolute value of N({i, j})] [greater than or equal to] 2t - 1(t [greater than or equal to] 3) for each pair of nodes {i, j} [subset] V and [absolute value of N(i)] [greater than or equal to] t + 1 for each node i [member of] V, then S is a t/t-diagnosable system.

Proof. Assume that the system is not t/t-diagnosable. By Theorem 6, there exist two sets [S.sub.1], [S.sub.2] [subset] V with [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]] = t and [S.sub.1] [not equal to] [S.sub.2] such that none of the conditions of Lemma 5 is satisfied. Let [absolute value of [S.sub.1] - [S.sub.2]] = [absolute value of [S.sub.2] - [S.sub.1]] = p, 1 [less than or equal to] p [less than or equal to] t. Consider the following cases.

Case 1 (p = 1). Let {i} = [S.sub.1] - [S.sub.2], {j} = [S.sub.2] - [S.sub.1]. Since [absolute value of N({i, j})] [greater than or equal to] 2t - 1 and [absolute value of [S.sub.1] [intersection] [S.sub.2]] = t - 1, note that when t [greater than or equal to] 3, [absolute value of N({i, j})] - [absolute value of [S.sub.1] [intersection] [S.sub.2]] [greater than or equal to] 2t - 1 - (t -1) = t [greater than or equal to] 3, there exist at least two nodes k, l [member of] V - [S.sub.1] - [S.sub.2] such that (i, k) [member of] E and (i, I) [member of] E or (j, k) [member of] E and (j, l) [member of] E. Without loss of generality, let (i, k) [member of] E and (i, l) [member of] E. Since [absolute value of N({k, l})] [greater than or equal to] 2t - 1 and [absolute value of [S.sub.1] [union] [S.sub.2] = t + 1, note that when t [greater than or equal to] 3, [absolute value of N({k, l})] - [absolute value of [S.sub.1] [union] [S.sub.2]] [greater than or equal to] 2t - 1 - (t + 1) = t - 2 [greater than or equal to] 1, there exists a node m [member of] V - [S.sub.1] - [S.sub.2] such that (m, k) [member of] E or (m, l) [member of] E. Then for the three nodes m, k, i or m, j, i, condition (1) of Lemma 5 is satisfied, a contradiction.

Case 2 (p [greater than or equal to] 2). Let {i, j] [subset not equal to] [S.sub.1] - [S.sub.2]. Since [absolute value of N({i, j})] [greater than or equal to] 2t - 1 and [absolute value of [S.sub.1] [union] [S.sub.2] - {i, j}] [less than or equal to] 2t - 2, there exists a node k [member of] V - [S.sub.1] - [S.sub.2] such that (i, k) [member of] E or (j, k) [member of] E. Without loss of generality, let (i, k) [member of] E. Since [absolute value of N({i,k})] [greater than or equal to] 2t - 1 and [absolute value of N(k)] [greater than or equal to] t + 1, there must exist a node I [member of] V - [S.sub.2] such that (l, k) [member of] E. Then for i, k, l, at least one condition of Lemma 5 (condition (1) or (2)) is satisfied, a contradiction.

Note that, for a given system, by using Theorems 10 and 11, we are able to obtain a range from [t.sub.min] to [t.sub.max] conveniently, in which the system is at least [t.sub.min/[t.sub.min]-diagnosable and at most [t.sub.max]/[t.sub.max]-diagnosable. In other words, for a system S, let G = (V, E) denote its diagnostic graph, m = min{[absolute value of N(i, j)]i, j [member of] V}, M = max{[absolute value of N(i, j)]i, j [member of] V]; then we conclude that S is at least m/m-diagnosable and is at most M/M-diagnosable.

4.1. n-Dimensional Hypercube. An n-dimensional hypercube [Q.sub.n] has [2.sup.n] nodes and each node is labeled by an n-bit binary string. Two nodes are adjacent if and only if their labels differ in exactly one bit position [21]. Since for each adjacent pair of nodes {i, j} [subset] [Q.sub.n], [absolute value of N({i, j})] = 2n - 2 < 2n - 1, by Theorem 10 we have that the n-dimensional hypercube is not (2n - 1)/(2n - 1)-diagnosable. Next, we shall show that an n-dimensional hypercube is (2n - 2)/(2n - 2)-diagnosable.

Lemma 12 (see [22]). Let G = (V, E) be the graph of a hypercube of n dimension and X [subset] V with [absolute value of X] = k, 0 < k [less than or equal to] n + 1, then N(X) [greater than or equal to] kn - k(k + 1)/2 + 1.

Theorem 13. Ann-dimensional (n [greater than or equal to] 6) hypercube [Q.sub.n], denoted by G = (V, E), is a (2n - 2)/(2n - 2)-diagnosable system.

Proof. Assume that, to the contrary, an n-dimensional hypercube [Q.sub.n] is not a (2n - 2)/(2n - 2)-diagnosable system. Then there exist two sets of nodes [S.sub.1], [S.sub.2] [subset or equal to] [Q.sub.n] with [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]] = 2n - 2 and [S.sub.1] [not equal to] [S.sub.2], such that none of the three conditions of Lemma 5 is satisfied. Let [absolute value of [S.sub.1] - [S.sub.2]] = [absolute value of [S.sub.2] - [S.sub.1]] = p, 1 [less than or equal to] p [less than or equal to] 2n - 2. Consider the following cases.

Case 1 (p = 1). Let {i} = [S.sub.1] - [S.sub.2], {j} = [S.sub.2] - [S.sub.1]. Since [absolute value of N({i, j})] [greater than or equal to] 2n - 2 and [absolute value of [S.sub.1] [intersection] [S.sub.2]] = 2n - 3, there existsanode k [member of] V - [S.sub.1] - [S.sub.2] such that (i, k) [member of] E or (j, k) [member of] E. Without loss of generality, let (i, k) [member of] E; then N(k) - {i} [subset or equal to] [S.sub.2]. Otherwise there exists a node v [member of] V - [S.sub.1] - [S.sub.2] such that the three nodes i, j, and k satisfy condition (1) of Lemma 5, a contradiction. We claim that N(i) - {k} [subset not equal to] [S.sub.2]. Otherwise, note that (N(k) - {i}) [intersection] (N(i) - {k}) = [phi] and [absolute value of N(k) - {i}] + [absolute value of N(i) - {k}] = [absolute value of [S.sub.2]] = 2n - 2. Combining the address structure of [Q.sub.n](n [greater than or equal to] 6), we have that there exist two nodes a, b [member of] V - [S.sub.1] - [S.sub.2] such that for nodes a, b, j, condition (1) of Lemma 5 is satisfied. Therefore N(i) - {k} [subset not equal to] [S.sub.2]. Let l [member of] N(i) - {k} and l [subset not equal to] [S.sub.2]. Let X = {i, k, l}; we have [absolute value of N(X)] [greater than or equal to] 3n-5. So, [absolute value of N(X)] - [absolute value of [S.sub.2]] [greater than or equal to] 3n-5 - (2n-2) = n - 3 [greater than or equal to] 3(n [greater than or equal to] 6). Without loss of generality, let v [member of] N(X) and v [not member of] [S.sub.2]. We claim that v [member of] N(i). Otherwise, for nodes v, i, k(l), condition (1) of Lemma 5 is satisfied. Thus, v [member of] N(i); then let Y = {v, l, k}, according to Lemma 12, we have [absolute value of N(Y)] [greater than or equal to] 3n-5. Let [eta] = [absolute value of N(X)] - [absolute value of [S.sub.1] [union] [S.sub.2]] [greater than or equal to] 3n - 5 - (2n - 1) = n - 4. When n [greater than or equal to] 6,we have [eta] [greater than or equal to] 2. Without loss of generality, let u [member of] N(Y) and u [not member of] ([S.sub.1] [union] [S.sub.2]). Then for nodes u, i, k(l or v), condition (1) of Lemma 5 is satisfied, a contradiction.

Case 2 (p = 2). Let {i,j} = [S.sub.1] - [S.sub.2], {i', j'} = [S.sub.2] - [S.sub.1], and X = {i, j, i', j'}. By Lemma 12 we know that N(X) [greater than or equal to] 4n-9 and [absolute value of [S.sub.1] [intersection] [S.sub.2]] = 2n-4. [absolute value of N(X)]-[absolute value of [S.sub.1] [intersection] [S.sub.2]] [greater than or equal to] 4n-9-(2n-4) = 2n-5 [greater than or equal to] 7(n [greater than or equal to] 6). Let Y = {a, b, c, d} with Y [subset] N(X) and Y [intersection] ([S.sub.1] [intersection] [S.sub.2]) = [phi]. According to Lemma 12, we have [absolute value of N(Y)] [greater than or equal to] 4n - 9, [absolute value of N(X)]-[absolute value of [S.sub.1] [union] [S.sub.2]] [greater than or equal to] 4n-9-2n=2n-9 [greater than or equal to] 3(n [greater than or equal to] 6). Thus, there exists a node v such that v [member of] N(Y) and v [not member of] ([S.sub.1] [union] [S.sub.2]). Without loss of generality, let (a, i) [member of] E and (a, v) [member of] E. Then, for nodes a, v, i, condition (1) of Lemma 5 is satisfied, a contradiction.

Case 3 (3 [less than or equal to] p [less than or equal to] 2n-7). Since [absolute value of [S.sub.1] -[S.sub.2]] = [absolute value of [S.sub.2]-[S.sub.1]] = p(3 [less than or equal to] p [less than or equal to] 2n - 7), there always exists a set X [subset or equal to] ([S.sub.1] - [S.sub.2]) [union] ([S.sub.2] -[S.sub.1]) with [absolute value of X] = 6 such that N(X) [greater than or equal to] 6n-20. Note that [absolute value of [S.sub.1] [union] [S.sub.2] - X] [greater than or equal to] 4n-9-6 = 4n-15 and [absolute value of N(X)]-[absolute value of [S.sub.1] [union][S.sub.2]-X] [greater than or equal to] 6n-20- (4n-15) = 2n-5 [greater than or equal to] 7(n [greater than or equal to] 6). Then there exists a set Y = {a, b, c, d, e, f, g} such that Y [subset] N(X) and Y [intersection] ([S.sub.1] [union] [S.sub.2]) = [phi]. According to Lemma 12, we have N(Y) [greater than or equal to] 6n - 20. [absolute value of N(Y)] - [absolute value of [S.sub.1] [union] [S.sub.2]] [greater than or equal to] 6n-20-(2n-2+p) [greater than or equal to] 4n-18-p [greater than or equal to] 4n-18-(2n-7) = 2n-11 [greater than or equal to] 1(n [greater than or equal to] 6). Thus, there exists a node v such that v [member of] N(Y) and v [not member of] ([S.sub.1] [union] [S.sub.2]). Without loss of generality, let i [member of] X, (a, i) [member of] E, and (a, v) [member of] E. Then for nodes a, v, i, condition (1) of Lemma 5 is satisfied, a contradiction.

Case 4 (2n - 6 [less than or equal to] p [less than or equal to] 2n - 2). Since [absolute value of [S.sub.1] - [S.sub.2]] = [absolute value of [S.sub.2] - [S.sub.1]] = p, when n [greater than or equal to] 6, we have p [greater than or equal to] 6. Then there always exists a set X [subset or equal to] ([S.sub.1] - [S.sub.2]) with [absolute value of X] = 6 such that N(X) [greater than or equal to] 6n - 20. [absolute value of N(X)] - [absolute value of [S.sub.1] [union] [S.sub.2] - X] [greater than or equal to] 6n - 20 - (4n - 10) = 2n- 10 [greater than or equal to] 2(n [greater than or equal to] 6). Then there exists a set Y = {a, b} [subset] N(X) such that Y [intersection] ([S.sub.1] [union] [S.sub.2]) = [phi]. According to Lemma 12, we have N(Y) [greater than or equal to] 2n-2. [absolute value of N(Y)] - [absolute value of [S.sub.1] [intersection] [S.sub.2]] [greater than or equal to] 2n- 2-4 = 2n-6 [greater than or equal to] 6(n [greater than or equal to] 6). Thus, there exists a set Z [subset] N(Y) with [absolute value of Z] = 3 such that Z [subset] [S.sub.1] - [S.sub.2] or Z [subset] [S.sub.2] - [S.sub.1]. Note that Z [subset] N(Y), [absolute value of Z] = 3 and Y [subset] N(Z), [absolute value of Y] = 2. Thus, there must exist one node in Y connecting two nodes in Z. Without loss of generality, let i, j [member of] Z, (a, i) [member of] E, and (a, j) [member of] E; then, for nodes a, i, j, condition (2) of Lemma 5 is satisfied, a contradiction.

Above all, an n-dimensional (n [greater than or equal to] 6) hypercube [Q.sub.n] is a (2n - 2)/(2n - 2)-diagnosable system.

4.2.2D and 3D Mesh. A 2D mesh contains [n.sup.2] nodes and each node is labeled with a two-bit string such as [a.sub.ij] (0 [less than or equal to] i [less than or equal to] n - 1, 0 [less than or equal to] j [less than or equal to] n - 1). Two nodes [a.sub.ij] and [a.sub.i'j'] are adjacent if and only if one of the following conditions is satisfied.

(i) (i + 1)mod n = i and j = j'.

(ii) (i - 1)mod n = i' and j = j'.

(iii) (j + 1)modn = j' and i = i'.

(iv) (j - 1)modn = j' and i = i'.

Let G = (V, E) be the graph of a 2D mesh with [n.sup.2] nodes and X [subset] V with [absolute value of X] = k, 0 < k [less than or equal to] [(n - 1).sup.2]; let N(X, k) denote the value of [absolute value of N(X)].

Observe that N(X, 2) [greater than or equal to] 6, N(X, 3) [greater than or equal to] 7, N(X,4) [greater than or equal to] 8, N(X,6) [greater than or equal to] 9, and N(X, 8) [greater than or equal to] 11.

Lemma 14. Let G = (V, E) be the graph of a 2D mesh with [n.sup.2] nodes, X [subset] V; if any two nodes of X are not adjacent, then N(X, 3) [greater than or equal to] 8, N(X, 4) [greater than or equal to] 9, N(X, 6) [greater than or equal to] 13.

Proof. Using exhaustive method, we can easily get that the conclusion is true.

For each adjacent pair of nodes {i, j} [subset] V, we always have [absolute value of N({i, j})] = 6 < 7, by Theorem 10 we have that the 2D mesh with [n.sup.2] nodes is not 7/7-diagnosable. Next, we shall show that a 2D mesh with [n.sup.2] nodes is a 6/6-diagnosable system.

Theorem 15. A 2D mesh with [n.sup.2] nodes (n [greater than or equal to] 5), denoted by G = (V, E), is a 6/6-diagnosable system.

Proof. Assume that, to the contrary, a 2D mesh with [n.sup.2] nodes, denoted by G = (V, E), is not a 6/6-diagnosable system. Then there exist two sets of nodes [S.sub.1], [S.sub.2] [subset] V with [absolute value of [S.sub.1]] = [absolute value of [S.sub.2]] = 6 and [S.sub.1] [not equal to] [S.sub.2], such that for [S.sub.1] and [S.sub.2] none of the three conditions of Lemma 5 is satisfied. Let [absolute value of [S.sub.1] - [S.sub.2]] = [absolute value of [S.sub.2] - [S.sub.1]] = p, 1 [less than or equal to] p [less than or equal to] 6. Consider the following cases.

Case 1 (p = 1). Let {i} = [S.sub.1] -[S.sub.2], {j} = [S.sub.2]-[S.sub.1]. Since [absolute value of N({i, j})] [greater than or equal to] 6 and [absolute value of [S.sub.1] [intersection] [S.sub.2]] = 5, there exists a node k [member of] V - [S.sub.1] - [S.sub.2] such that (i, k) [member of] E or (j, k) [member of] E. Without loss of generality, let (i, k) [member of] E; then we have N(k) - {i} [subset or equal to] [S.sub.2]. If N(i') - {k} [subset or equal to] [S.sub.2], note that (N(k) - {i}) [intersection] (N(i) - {k}) = [phi]; this implies that [absolute value of N(k) - {i}] + [absolute value of N(i) - {k}] = [absolute value of [S.sub.2]] = 6. Then [S.sub.2] = (N(k) - {i}) [union] (N(i) - {k}) = N({i, k}). So, j [member of] N({i, k}). Thus, there always exist two nodes a, b [member of] V - [S.sub.1] - [S.sub.2] such that, for nodes a, b, j, condition (1) of Lemma 5 is satisfied. Therefore, N(i) - {k} [subset not equal to] [S.sub.2]. Let l [member of] N(i)-{k}, l [not member of] [S.sub.2], X = {i, k, l}; we have N(X, 3) [greater than or equal to] 7. Then there exists a node m [member of] V - [S.sub.1] - [S.sub.2] such that m [member of] N(X). We claim that (i, m) [member of] E. Otherwise, if (k, m) [member of] E or (l, m) [member of] E, then condition (1) of Lemma 5 is satisfied, a contradiction. Now, let Y = {k, l, m}; then Y [subset] N(i). This implies that any two nodes of Y are not adjacent, and by Lemma 14 we have that N(Y, 3) [greater than or equal to] 8. In other words, there exists a node q [member of] V - [S.sub.1] - [S.sub.2] such that q [member of] N(Y). Then, for nodes i, q, l(k or m), condition (1) of Lemma 5 is satisfied, a contradiction.

Case 2 (p = 2). Let {i, j} = [S.sub.1] - [S.sub.2], {i', j'} = [S.sub.2] - [S.sub.1], and X = {i, j, i', j'}. We have that N(X, 4) [greater than or equal to] 8 and [absolute value of [S.sub.1] [intersection] [S.sub.2]] = 4, and then [absolute value of N(X)] - [absolute value of [S.sub.1] [intersection] [S.sub.2]] [greater than or equal to] 8 - 4 = 4. So, there exist four nodes a, b, c, d [member of] V - [S.sub.1] - [S.sub.2] such that {a, b, c, d} [subset] N(X). Let Y = {a, b, c, d}; we claim that any two nodes of Y are not adjacent. Otherwise, for nodes i(j or i' or j') and the adjacent pair of Y, condition (1) of Lemma 5 is satisfied, a contradiction. By Lemma 14 we have that N(Y, 4) [greater than or equal to] 9. Thus, there exists a node k [member of] V - [S.sub.1] - [S.sub.2] such that k [member of] N(Y). Without loss of generality, let (k, a) [member of] E; then, for nodes k, a, i(j or i' or j'), condition (1) of Lemma 5 is satisfied, a contradiction.

Case 3 (p = 3). Since [absolute value of [S.sub.1] - [S.sub.2]] = [absolute value of [S.sub.2] - [S.sub.1]] = p = 3, let X = ([S.sub.1] - [S.sub.2]) [union] ([S.sub.2] - [S.sub.1]) with [absolute value of X] = 6 and N(X) [greater than or equal to] 9. Note that [absolute value of [S.sub.1] [union] [S.sub.2]-X] = 9-6 = 3; then [absolute value of N(X)]-[absolute value of [S.sub.1] [union] [S.sub.2]-X] [greater than or equal to] 9-3 = 6. A similar argument to case 2 can be used in the rest.

Case 4 (p > 3). Since [absolute value of [S.sub.1] - [S.sub.2]] = [absolute value of [S.sub.2] - [S.sub.1]] = p [greater than or equal to] 4, there always exists a set X = ([S.sub.1] - [S.sub.2]) [union] ([S.sub.2] - [S.sub.1]) with [absolute value of X] = 8 and [absolute value of N(X)] [greater than or equal to] 11. Note that [absolute value of [S.sub.1] [union] [S.sub.2] - X] [less than or equal to] 12 - 8 = 4; then [absolute value of N(X)] - [absolute value of [S.sub.1] [union] [S.sub.2] - X] [greater than or equal to] 11 - 4 = 7. A similar conclusion can be obtained by the similar analysis of case 2.

Above all, a 2D mesh with [n.sup.2] nodes (n [greater than or equal to] 5) is a 6/6-diagnosable system.

Furthermore, by a similar analysis to the situation of 2D mesh, we can conclude that the 3D mesh with [n.sup.3] nodes (n [greater than or equal to] 4) is 10/10-diagnosable.

4.3. Permutation Star Graph. An n-dimensional star graph, denoted by [S.sub.n], is a graph with the node set [mathematical expression not reproducible] is a permutation of 1, 2, 3, ..., n} and the edge set [mathematical expression not reproducible]. There is an edge between two nodes of [S.sub.n] if and only if they can be obtained from each other by swapping the leftmost number with one of the other n - 1 numbers. The cn-number of two nodes x, y is the number of common neighbors they share, denoted by cn(w, v). Let cn([S.sub.n])=maxjcn(u, v)|w, v [member of] V}; by [15], we have cn([S.sub.n]) = 1.

For each adjacent pair of nodes {i, j} [subset] [S.sub.n], we always have [absolute value of N({i, j})] = 2n - 4 < 2n - 3. By Theorem 10, we have that the n-dimensional star graph is not (2n-3)/(2n-3)-diagnosable. Next, we shall show that an n-dimensional star graph is (2n - 4)/(2n - 4)-diagnosable system.

Theorem 16. An n-dimensional(n [greater than or equal to] 5) star graph [S.sub.n], denoted by G = (V, E), is a (2n - 4)/(2n - 4)-diagnosable system.

Proof. Assume that, to the contrary, an n-dimensional star graph [S.sub.n] is not a (2n - 4)/(2n - 4)-diagnosable system. Then there exist two sets of nodes [U.sub.1], [U.sub.2] [subset] [S.sub.n] with [absolute value of [U.sub.1]] = [absolute value of [U.sub.2]] = 2n - 4 and [U.sub.1] [not equal to] [U.sub.2]; we have that for [U.sub.1] and [U.sub.2] none of the three conditions of Lemma 5 is satisfied. Let [absolute value of [U.sub.1] - [U.sub.2]] = [absolute value of [U.sub.2] - [U.sub.1]] = p, 1 [less than or equal to] p [less than or equal to] 2n - 4. Consider the following cases.

Case 1 (p = 1). Let {i} = [U.sub.1] - [U.sub.2], {j} = [U.sub.2] - [U.sub.1]. Since [absolute value of N({i,j})] [greater than or equal to] 2n-4 and [absolute value of [U.sub.1] [intersection] [U.sub.2]] = 2n-5, there exists a node k [member of] V - [U.sub.1] - [U.sub.2] such that (i, k) [member of] E or (j, k) [member of] E. Without loss of generality, let (i, k) [member of] E; then we have N(k) - {I} [subset or equal to] [U.sub.2]. If N(i) - {k} [subset or equal to] [U.sub.2], note that (N(k) - {i}) [intersection] (N(i) - {k}) = 0 and [absolute value of N(k) - {i}] + [absolute value of N(i) - {k}] = [absolute value of [U.sub.2]] = 2n - 4; then [U.sub.2] = ((N(k) - {I}) [union] (N(i) - {k}) = N({i,k}), j [member of] N({i,k}). Without loss of generality, let (j, k) [member of] E; note that cn([S.sub.n]) = 1; then N(j) [member of] V - ([U.sub.1] [union] [U.sub.2]). Let v [member of] N(j) - {k}, and then N(v) - {j} c[subset]V - ([U.sub.1] [union] [U.sub.2]). In other words, there exists a node u [member of] N(v) - {j} such that u [member of] V - ([U.sub.1] [union] [U.sub.2]). Then, for nodes j, u, v, condition (1) of Lemma 5 is satisfied. Therefore, N(i) - {k} [subset not equal to] [U.sub.2]. Let l [member of] N(i) - {k}; then l [not member of] [U.sub.2]. Let X = {i, k, l}; by the definition of n-dimensional star graph, we have N(x) [greater than or equal to] 3n - 7 and [absolute value of N(X)] - [absolute value of [U.sub.2]] [greater than or equal to] 3n - 7 - (2n - 4) = n-3 [greater than or equal to] 2(n [greater than or equal to] 5). Then there exists anode v [member of] V-[U.sub.1] - [U.sub.2] such that v [member of] N(X). We claim that (v, 1) [member of] E. Otherwise, for nodes i, v, k(l), condition (1) of Lemma 5 is satisfied, a contradiction. Letting Y = {v, l, k}, since Y [subset] N(i), by the definition of n-dimensional star graph, we have N(Y) [greater than or equal to] 3n-5. Then we have [absolute value of N(Y)]-[absolute value of [U.sub.1] [union] [U.sub.2]] [greater than or equal to] 3n-5-(2n-3) = n-2 [greater than or equal to] 3(n [greater than or equal to] 5).Hence, there exists a node m [member of] V - [U.sub.1] - [U.sub.2] such that m [member of] N(Y). Without loss of generality, let (m, v) [member of] E; then, for nodes m, v, i, condition (1) of Lemma 5 is satisfied, a contradiction.

Case 2 (p = 2). Let {i, j} = [U.sub.1] - [U.sub.2], {i',j'} = [U.sub.2] - [U.sub.1] and X = {i, j, i', j'}. By the definition of star graph we know that N(X) [greater than or equal to] 4n - 10 and [absolute value of [U.sub.1] - [U.sub.2]] = 2n-6. Then [absolute value of N(X)] - [absolute value of [U.sub.1] [intersection] [U.sub.2]] [greater than or equal to] 4n - 10 - (2n - 6) = 2n - 4 [greater than or equal to] 4(n [greater than or equal to] 4). There exist four nodes a, b, c, d [member of] V - [U.sub.1] - [U.sub.2] such that [a, b, c, d} [subset] N(X). Let Y = [a, b, c, d}; then N(Y) [greater than or equal to] 4n-10, [absolute value of N(Y)] - [absolute value of [U.sub.1] [union] [U.sub.2]] [greater than or equal to] 4n - 10 - (2n - 2) = 2n - 8 [greater than or equal to] 2(n [greater than or equal to] 5). Therefore, there exists a node v [member of] V - [U.sub.1] - [U.sub.2] such that v [member of] N(Y). Without loss of generality, let (a, v) [member of] E; then, for nodes a, v, i, condition (1) of Lemma 5 is satisfied, a contradiction.

Case 3 (2 < p < 2n-4). Since [absolute value of [U.sub.1] - [U.sub.2]] = [absolute value of [U.sub.2] - [U.sub.1]] = p [greater than or equal to] 3, there always exists a set X [subset or equal to] ([U.sub.1] - [U.sub.2]) [intersection] ([U.sub.2]-[U.sub.1]) with [absolute value of X] = 6 such that N(X) [greater than or equal to] 6n - 18. Note that [absolute value of [U.sub.1] [union] [U.sub.2]-X] [less than or equal to] 4n-9-6 = 4n-15 and [absolute value of N(X)]-[absolute value of [U.sub.1] [intersection] [U.sub.2]-X] [greater than or equal to] 6n-18-(4n-15) = 2n-3 [greater than or equal to] 7 (n [greater than or equal to] 5). Then there exist six nodes a, b, c, d, e, f [member of] V-[U.sub.1]-[U.sub.2] and [a, b, c, d, e, f} [subset] N(X). Let Y = [a, b, c, d, e, f}, and then [absolute value of N(Y)] - [U.sub.1] [intersection] [U.sub.2] - X] [greater than or equal to] 6n - 18 - (4n - 9) = 2n - 9 [greater than or equal to] 1(n [greater than or equal to] 5). Therefore, there exists a node m [member of] V - [U.sub.1] - [U.sub.2] such that m [member of] N(Y). Without loss of generality, let (a, m) [member of] E, then for nodes a, m, i(i [member of] X and i [member of] N(Y)), condition (1) of Lemma 5 is satisfied, a contradiction.

Case 4 (p = 2n-4). Since [absolute value of [U.sub.1]-[U.sub.2]] = [absolute value of [U.sub.2]-[U.sub.1]] = p = 2n-4, there always exists a set X [subset or equal to] ([U.sub.1] [union] [U.sub.2]) with [absolute value of X] = 6 such that N(X) [greater than or equal to] 6n-18. Then[absolute value of N(X)]-[absolute value of [U.sub.1] [union] [U.sub.2]-X] [greater than or equal to] 6n-18-(4n-14) = 2n-4 [greater than or equal to] 6(n [greater than or equal to] 5).Hence, there exists a node v [member of] V - [U.sub.1] - s[U.sub.2] such that v [member of] N(X). If there exists a node u [member of] N(v) such that u [member of] V-[U.sub.1]-[U.sub.2], then, for nodes u, v, i(i [member of] X and i [member of] N(v)), condition (1) of Lemma 5 is satisfied, a contradiction. Thus, we have N(v) [subset] ([U.sub.1] [union] [U.sub.2]). Note that N(v) = n- 1 [greater than or equal to] 4(n [greater than or equal to] 5); then there must exist two nodes k, l [member of] N(v) such that either k, l [member of] [U.sub.1] or k, l [member of] [U.sub.2]. Thus, for nodes v, k, l, condition (2) or (3) of Lemma 5 is satisfied, a contradiction.

Above all, an n-dimensional star graph [S.sub.n] (n [greater than or equal to] 5) is (2n - 4)/(2n - 4)-diagnosable system.

5. Experiments and Comparisons

Diagnosability plays an important role in the reliability of an interconnection network. For an interconnection network, the larger the diagnosability it has, the stronger the self-diagnostic capability it has. In this section, we show that the t/t-diagnosable strategy proposed in the paper is superior to the traditional t-diagnosable strategy by comparing t/t-diagnosability and t-diagnosability for the hypercube networks (the star networks).

For the sake of convenience, let t([Q.sub.n]) (respectively, t/t([Q.sub.n])) represent the t-diagnosability (respectively, t/t-diagnosability) of n-dimensional hypercube networks and t([S.sub.n]) (respectively, t/t([S.sub.n])) represent the t-diagnosability (respectively, t/t-diagnosability) of n-dimensional star networks. According to [11], it is easily obtained that t([Q.sub.n]) = n,t([S.sub.n]) = n - 1. By Theorem 10 and Theorem 13, we have that t/t([Q.sub.n]) = 2n - 2, t/t([S.sub.n]) = 2n-4. This implies that that the t/t-diagnosability of n-dimensional hypercube network is 2n- 2 which is almost twice as large as n, t-diagnosability of [Q.sub.n], and t/t-diagnosability of [S.sub.n] is 2n-4 which is almost twice as large as n, the t-diagnosability of [S.sub.n]. In order to compare expediently their sizes, we have made a table (namely, Table 1) for 5 [less than or equal to] n [less than or equal to] 15. By Table 1, it is easily found that for each n [greater than or equal to] 5 the number of Colum 3 (t/t([Q.sub.n]) is larger than the number of Column 1 (t([Q.sub.n])), and the number of Column 4 (t/t([S.sub.n]) is larger than the number of Column 3 (t([S.sub.n])). For example, n = 14, t/t([Q.sub.n]) = 26 is 12 more than 14, t([Q.sub.n]), and t/t([S.sub.n]) = 24 is 11 more than 13, t([S.sub.n]). In order to compare the growth trend of t-diagnosability and t/t-diagnosability for hypercube network and star network for variable n, we have made Figures 3 and 4, where Figure 3 illustrates the growth trend of t-diagnosability and t/t-diagnosability for hypercube network, and Figure 4 illustrates the growth trend of t-diagnosability and t/t-diagnosability for star network. Figures 3 and 4 and the data in Table 1 show that, for an n-dimensional interconnection network, our diagnostic strategy is superior to the classical t-diagnosable strategy proposed by [11]. For example, for a 10-dimensional hypercube network, when there are more than 10 faulty nodes in the system, the classical t-diagnosable strategy proposed by [11] does not work. However, our t/t-diagnosable strategy proposed in this paper still works provided the number of faulty nodes in the network does not exceed 18.

6. Conclusion

This paper proposes characterizations of t/t-diagnosable systems under the comparison model. By analyzing characterizations of t/t-diagnosable systems we discover some properties of allowable fault set, which are significant in exploring the AFS in a system under the comparison model. Furthermore, we also introduce a method to find out a range from [t.sub.min] to [t.sub.max], in which the system is at least [t.sub.min]/[t.sub.min] diagnosable and at most [t.sub.max]/[t.sub.max]-diagnosable. Also by using above method and the characterization of t/t-diagnosable systems we figure out the t/t-diagnosability of some practical interconnection networks such as n-dimensional hypercube, 2D (3D) mesh, and n-dimensional permutation star graph.

https://doi.org/10.1155/2018/7168628

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that they no conflicts of interest.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant no. 61363002 and the Natural Science Foundation of Guangxi Zhuang Autonomous Region of China under Grant no. 2016GXNSFAA380134.

References

[1] F. P. Preparata, G. Metze, and R. T. Chien, "On the Connection Assignment Problem of Diagnosable Systems," IEEE Transactions on Electronic Computers, vol. EC-16, no. 6, pp. 848-854, 1967.

[2] A. K. Somani, "A Generalized Theory for System Level Diagnosis," IEEE Transactions on Computers, vol. C-36, no. 5, pp. 538-546, 1987.

[3] S.-L. Peng, C.-K. Lin, J. J. Tan, and L.-H. Hsu, "The g-good-neighbor conditional diagnosability of hypercube under PMC model," Applied Mathematics and Computation, vol. 218, no. 21, pp. 10406-10412, 2012.

[4] L.-C. Ye and J.-R. Liang, "Five-Round Adaptive Diagnosis in Hamiltonian Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 9, pp. 2459-2464, 2015.

[5] T. Araki and Y. Shibata, "(t, k)-diagnosable system: A generalization of the PMC models," IEEE Transactions on Computers, vol. 52, no. 7, pp. 971-975, 2003.

[6] J. Liang and Q. Zhang, "The t/s-diagnosability of hypercube networks under the PMC and comparison models," IEEE Access, vol. 5, pp. 5340-5346, 2017.

[7] G. Y. Chang, G. J. Chang, and G. H. Chen, "Diagnosability of regular networks," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 314-323, 2005.

[8] J. R. Liang, N. Zhou, and L. Yun, "A new t/k-diagnosis algorithm for n-dimensional hypercube network under the comparison model," Journal of Systems Engineering and Electronics, vol. 29, no. 1, pp. 216-222, 2018.

[9] J. Maeng and M. Malek, "A comparison connection assignment for self-diagnosis of multiprocessor systems," in proceeding of the eleventh Int'l Symposium Fault-Tolerant Computing, pp. 173-175, 1981.

[10] M. Malek, "A comparison connection assignment for diagnosis of multiprocessor systems," in Proceedings of the the 7th annual symposium, pp. 31-36, La Baule, United States, May 1980.

[11] A. Sengupta and A. T. Dahbura, "On self-diagnosable multiprocessor systems: diagnosis by the comparison approach," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.

[12] T.-L. Ye and S.-Y. Hsieh, "A scalable comparison-based diagnosis algorithm for hypercube-like networks," IEEE Transactions on Reliability, vol. 62, no. 4, pp. 789-799, 2013.

[13] D. Wang, "Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 48, no. 12, pp. 1369-1374, 1999.

[14] S.-Y. Hsieh and Y.-S. Chen, "Strongly diagnosable product networks under the comparison diagnosis model," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 57, no. 6, pp. 721-732, 2008.

[15] Q. Zhu, G. Guo, and D. Wang, "Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 63, no. 7, pp. 1847-1851, 2014.

[16] L.-C. Ye, J.-r. Liang, and H.-X. Lin, "A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 65, no. 9, pp. 2884-2888, 2016.

[17] A. D. Friedman, "A new measure of digital system diagnosis," in Proceedings of the of Fifth International Sympsium on Fault Tolerant Computing, pp. 167-170, 1975.

[18] S. L. Hakimi and A. T. Amin, "Characterization of Connection Assignment of Diagnosable Systems," IEEE Transactions on Computers, vol. C-23, no. 1, pp. 86-88, 1974.

[19] K. Y. Chwa and S. L. Hakimi, "On fault identification in diagnosable systems," Institute of Electrical and Electronics Engineers. Transactions on Computers, vol. 30, no. 6, pp. 414-422, 1981.

[20] C. L. Yang, G. M. Masson, and A. R. Leonetti, "On Fault Isolation and Identification in t1/t1-Diagnosable Systems," IEEE Transactions on Computers, vol. 35, no. 7, pp. 639-643, 1986.

[21] Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Transactions on Computers, vol. 37, no. 7, pp. 867-872, 1988.

[22] A. K. Somani and O. Peleg, "On diagnosability of large fault sets in regular topology-based computer systems," IEEE Transactions on Computers, vol. 45, no. 8, pp. 892-903, 1996.

Jiarong Liang (iD) (1,2) and Qian Zhang (iD) (1)

(1) School of Computer, Electronic and Information, Guangxi University, 530004, China

(2) Guangxi Key Laboratory of Multimedia Communications and Network Technology, 530004, China

Correspondence should be addressed to Jiarong Liang; 13977106752@163.com

Received 10 March 2018; Accepted 8 May 2018; Published 14 June 2018

Academic Editor: Allan C. Peterson

Caption: Figure 1: An interconnection topology graph G with 7 nodes.

Caption: Figure 2: The Venn diagram of graph G.

Caption: Figure 3: Comparison of classical diagnosability and t/t-diagnosability of n-dimensional hypercube networks.

Caption: Figure 4: Comparison of classical diagnosability and t/t-diagnosability of n-dimensional star networks.

Table 1: Comparison of classical diagnosability and t/t-diagnos-ability of n-dimensional hypercube and star network. n t([Q.sub.n]) t/t([Q.sub.n]) t([S.sub.n]) t/t([S.sub.n]) 5 5 8 4 6 6 6 10 5 8 7 7 12 6 10 8 8 14 7 12 9 9 16 8 14 10 10 18 9 16 11 11 20 10 18 12 12 22 11 20 13 13 24 12 22 14 14 26 13 24 15 15 28 14 26

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Liang, Jiarong; Zhang, Qian |

Publication: | Discrete Dynamics in Nature and Society |

Date: | Jan 1, 2018 |

Words: | 11575 |

Previous Article: | Stability and Hopf Bifurcation Analysis of a Plant Virus Propagation Model with Two Delays. |

Next Article: | Optimizing Price of Credit Default Swaps for Dynamic Project System of Public-Private Partnership. |

Topics: |