6

–––––––––––––––––––––––

Diagnosability of Multiprocessor Systems

Chia-Wei Lee and Sun-Yuan Hsieh

6.1   INTRODUCTION

The rapid advances in very-large-scale integration (VLSI) technology and wafer-scale integration (WSI) technology have made it possible to design and produce a multiprocessor system containing hundreds or even thousands of processors (nodes) on a single chip. As the number of nodes in a multiprocessor system increases, node fault identification in such systems becomes more crucial for reliable computing. The process of discriminating between faulty nodes and fault-free nodes in a system is called fault diagnosis. When a faulty node is identified, it is replaced by a fault-free node to maintain the system’s reliability. The diagnosability of a system is the maximum number of faulty nodes that the system can identify.

Determining the diagnosability of multiprocessor systems based on various strategies and models has been the focus of a great deal of research in recent years (e.g., see References 1–25). Among the proposed models, two of which, namely, the PMC model (after Preparata, Metze, and Chien [19] and the MM model (after Maeng and Malek [18]), are well known and widely used. In the PMC model, every node is capable of testing whether another node v is faulty if there exists a communication link between them. The PMC model assumes that the tests of faulty nodes performed by fault-free ones always return one and that the tests performed by faulty nodes return arbitrary results. The PMC model was also adopted in References 2, 4, 9, 15, and 16. In an attempt to have a more realistic representation of systems whose nodes have a rather complex structure, Barsi et al. [26] introduced a modification of the PMC model, namely, the BGM model (after Barsi, Grandoni, and Maestrini). The BGM model uses the same testing strategy as the PMC model, but it assumes that a faulty node is always tested as faulty regardless of the state of the tester. The BGM model was adopted in Reference 27.

In the MM model, on the other hand, a comparison is performed such that a node, chosen to be a comparator, monitors a pair of its neighboring nodes executing the same test input and compares their responses. We use (u, v)_w to represent a comparison (or test) in which nodes u and v are compared by w. For this reason, the MM model is also called the comparison diagnosis model. The method of the MM model takes advantage of the homogeneity of multiprocessor systems in which comparisons can be made easily. This approach seems attractive because no additional hardware is required and transient and permanent faults may be detected before completing the comparison program. There is no faulty voter problem because the comparator can also be tested. Moreover, the MM model can be considered to be a generalization of the PMC model because if for each comparison edge (u, v)_w, either w = u or w = v, then the comparison model corresponds directly to the PMC model [20]. Sengupta and Dahbura [20] further suggested a modification of the MM model, called the MM* model, in which any node has to test another two nodes if the former is adjacent to the latter two. The MM* model might be leading the way toward a polynomial-time diagnosis algorithm for the more general MM self-diagnosable systems, and complexity results on determining the level of diagnosability of systems. The MM* model was also adopted in References 4, 11, 13, 14, and 24.

6.2   FUNDAMENTAL CONCEPTS

An undirected graph (graph) G = (V, E) is composed of a node set V and an edge set E, where V is a finite set and E is a subset of {(u, v)|(u, v) is an unordered pair of V}. We also use V (G) and E (G) to denote the node set and edge set of G, respectively. For an edge (u, v), we call u and v the end nodes of the edge. A subgraph of G = (V, E) is a graph (V′ E′) such that V′ ⊆ Vand E′ ⊆E. Given U ⊆V (G), the subgraph of G induced by U is defined as G [U] = (U, {(u, v) ∈ E (G) |u, v ∈ U}). A multigraph is similar to an undirected graph, but there may exist multiple edges as well as self-loops between its nodes. A multiprocessor system can be modeled as a undirected graph G in which the nodes represent processors and the edges represent communication links.

The node connectivity (connectivity for short) of a graph G, denoted by κ(G), is the minimum size of a node set S such that G − S is disconnected or contains only one node.¹ A graph G is t-connected if κ(G) ≥ t. If (u, v) is an edge in a graph G, we say that u is adjacent to v. A neighbor of a node u in G = (V, E) is any node that is adjacent to u. Let V′ be a nonempty subset of V(G). The neighborhood set of node u in V ′ is defined as N_G(u, V′) = {v ∈ V′|(u, v) ∈ E(G)}. When V′ = V(G) − u, N_G(u, V') is reduced to N_G(u). We also call each node in N_G(u) a neighbor of u. The degree of a node u in a simple graph G, denoted by deg_G(u), is the number of edges incident to u, that is, deg_G (u) = |N_G(u)|. The minimum degree of a graph G = (V, E), denoted by δ(G), is min_u∈V{deg(u)}. For convenience, the subscript G can be deleted from the above notations if no ambiguity occurs. The relation between the minimum degree and the connectivity of a graph is formulated as follows:

Lemma 6.1   [28]    κ(G) ≤ δ(G).

The symmetric difference of two distinct sets, F₁and F₂, is defined as the set F₁Δ F₂ = (F₁− F2)∪(F₂− F₁).

6.2.1   The (1, 2)-Matching Composition Networks ((1, 2)-MCN)

A matching in a graph G is a set of nonloop edges with no shared end nodes. The nodes incident to the edges of a matching M are saturated by M; the others are unsaturated. Two matchings are distinct if they have no common edge. A perfect matching in a graph is a matching that saturates every node. The class of (1, 2)-MCNs is defined as follows.

Definition 6.1    Suppose that G1 and G₂are two graphs with the same number of nodes. Then, the resulting graph G, constructed from G₁ and G₂ by connecting V(G₁) and V(G₂) via an arbitrary perfect matching between V(G₁) and V(G₂) orvia two arbitrary distinct perfect matchings between V(G₁) and V(G₂), is called a(1, 2)-MCN.

Figure 6.1 illustrates (1, 2)-MCNs in which the bold lines and dotted lines represent two distinct perfect matchings. Note that each node v ∈ V(G₁) has exactly one neighbor (respectively, two neighbors) in V(G2) if G is constructed from G₁and G₂by connecting V(G₁) and V(G₂) via a perfect matching (respectively, two distinct perfect matchings) between V(G₁) and V(G₂). For a (1, 2)-MCN G, we use the notation G(G₁, G₂; PM1) (respectively, G(G₁, G₂; PM₂)) to represent that G is constructed from G₁and G₂by connecting V(G₁) and V(G₂) via a perfect matching PM₁(respectively, two distinct perfect matchings PM₂) between V(G₁) and V(G₂). Note that V(G(G₁, G₂; PM_k)) = V(G₁ ⋃ V(G₂ and E(G(G₁, G₂; PM_k)) = E(G₁) ⋃ E(G₂) ⋃ PM_k for k ∈ {1, 2}.

FIGURE 6.1. Examples of (1, 2)-MCNs.

6.2.2   The Diagnosis Model

A system G is said to be t-diagnosable if all faulty nodes can be identified without replacement, provided that the number of occurring faults does not exceed t. The diagnosability of G, denoted by d(G), refers to the maximum number of faulty nodes that can be identified by the system. In other words, a system is t-diagnosable if and only if each pair of distinct sets S₁, S₂⊆ V(G) with |S₁|, |S₂| ≤ t are distinguishable, and the diagnosability of G is max{t |G is t-diagnosable}.

6.2.2.1   The PMC Model   The PMC model diagnoses whether or not a node is faulty by sending a task from a node u to its neighbor v, and then checks the response. We use the notation to represent the test performed by u on v. The outcome of is 0 (respectively, 1) if u determines that v is fault free (respectively, faulty).

The test assignment of a system G can be modeled as a directed multigraph T = (V(G), L), where ∈ L implies that u and v are adjacent in G. The result of all tests in T = (V (G), L) is called a syndrome of the diagnosis. Given a syndrome σ, a set F ⊆ V(G) is said to be consistent with σ if and only if the following conditions hold:

1. If u ∈ V (G) − F and v ∈ F, then σ () = 1.

2. If u ∈ V (G) − F and v ∈ V (G)−F, then σ () = 0.

Formally, a syndrome is a function σ: L → {0, 1} such that F is consistent with σ.

Lemma 6.2   [29]    A system G = (V, E) is t-diagnosable if and only if, for any two distinct sets F₁, F₂⊂ V with |F₁| ≤ t, | F₂ | ≤ t, and F₁≠ F₂, there exists at least one test performed by a node u in V − (F₁∪ F₂) on a node v in F₁Δ F₂ (see Fig. 6.2).

The following two results related to t-diagnosable systems were reported by Hakimi and Amin [12] and Preparata et al. [19], respectively.

Lemma 6.3   [12] The following two conditions are sufficient for a system G containing n processors to be t-diagnosable:

1. n ≥ 2 t + 1.

2. κ (G) ≥ t.

FIGURE 6.2. Illustration of Lemma 6.2.

Lemma 6.4   [19]  Let G = (V, E) be a graph representation of a system, where V represents the processors and E represents the interconnections among the processors. Then, the following two conditions are necessary for G to be t-diagnosable:

1. n ≥ 2 t + 1.

2. δ (G) ≥ t.

6.2.2.2   The MM* Model  The MM model deals with the fault diagnosis by sending the same task from a node w to a pair of distinct neighbors, u and v, and then comparing their responses. In order to be consistent with the MM model, the following assumptions are made:

1. All faults are permanent.
2. A faulty processor produces incorrect output for each of its given tasks.
3. The outcome of a comparison performed by a faulty processor is unreliable.
4. Two faulty processors, when given the same inputs and task, do not produce the same output.

The comparison scheme of a system G can be modeled as a multigraph without self-loops, denoted by M(V(G), L), where L is the labeled-edge set. If nodes u and v can be compared by another node w, then there is an edge (u, v) associated with a label w, denoted by (u, v)_w, which represents a comparison (or test) in which nodes u and v are compared by w. An edge (u, v) may have multiple labels w₁, w₂,…,w_k, which means that u and v can be compared by each w_i for 1 ≤ i ≤ k. The result of all comparisons in M(V(G), L) is called the syndrome of the diagnosis. Briefly, a syndrome σ is a function from L to {0, 1}, and we use σ((u, v)_w) to represent the result of the comparison (u, v)_w in σ. In the special case of the MM model, called the MM* model, if u, v, w ∈ V(G) and (u, w), (v, w) ∈ E (G), then (u, v)_w must be in L. In other words, all possible comparisons of G must be in the comparison scheme of G. Hereafter, the results reported in this chapter are for systems under the MM* model. Figure 6.3 illustrates a system with its comparison schemes under the MM and MM* models.

Let G be a system with its comparison scheme M(V(G), L). Given a node u ∈ V(G), we define the order graph of u, denoted by G^u = (X^u, Y^u), as follows:

1. X^u = {v|(u, v) ∈ E(G)or(uv)_w∈ L}; that is, X^u consists of all the nodes that are adjacent to u or can be compared with u by any node w.
2. Y^u = {(v, w)|v, w ∈ X^u and (u, v)_w∈ L}; that is, edge (v, w) is in Y^uif u can be compared with v by node w.

The order of u, denoted by order_G(u), is defined as the cardinality of a minimum node cover of G^u. Given V′ ⊆ V (G), we define the probing set of V′, denoted by P(G, V'), to be the set {u ∈ V′|(u, v)_w∈ L and v, w ∈ V(G) − V′}. It means that all nodes in V′ can be compared with some node in V(G) − V′ by another node inV(G) − V' (Fig. 6.4).

For a given syndrome σ, S ⊆ V(G) is said to be a consistent fault set with σ if and only if the following conditions hold:

1. If u ∈ S and v, w ∈ V (G) − S, σ((u, v)_w) = 1.
2. If u, v ∈ S and w ∈ V (G) − S, σ((u, v)_w) = 1.
3. If u, v, w ∈ V (G) − S, σ((u, v)_w) = 0.

The syndrome σ can be produced from the situation where all nodes in S are faulty and all nodes in V(G) − S are fault-free. Because a faulty comparator w can lead to an unreliable result, the result by a faulty comparator may be 1 or 0 every time, and thus a given faulty set S may produce different syndromes. Let σ(S) denote all syndromes which S is consistent with.

Two distinct subsets S₁, S₂⊆ V(G) are said to be indistinguishable if σ(S₁) ∩ σ(S2) ≠ Ø; otherwise, S₁and S₂are said to be distinguishable. (S₁, S₂) is said to be an indistinguishable (respectively, a distinguishable) pair if S₁and S₂are indistinguishable (respectively, distinguishable).

Sengupta and Dahbura [20] proposed necessary and sufficient conditions for two distinct sets being distinguishable:

FIGURE 6.3 (a) A system G, (b) a comparison scheme of G under the MM model, and (c) a comparison scheme of G under the MM* model.

FIGURE 6.4. The order graphs G¹ and G ⁵ for graph G illustrated in Figure 6.3

Lemma 6.5   [20]  For any S₁, S₂⊂ V(G) and S₁ ≠ S₂, (S₁, S₂) is a distinguishable pair if and only if at least one of the following conditions is satisfied (see Fig. 6.5):

1. ∃ u, w ∈ V(G) − S₁−S₂and ∃ v ∈ (S₁−S₂) ∪ (S₂−S₁) such that (u, v)_w∈ L.
2. ∃ u, v ∈ S₁−S₂and ∃ w ∈ V(G) −S₁−S₂ such that (u, v)_w∈ L.
3. ∃ u, v ∈ S₂− S₁and ∃ w ∈ V (G) − S₁− S₂ such that (u, v)_w∈ L.

Lemma 6.6   [20]   A system G is t-diagnosable if and only if for each pair of sets S₁, S₂ ⊂ V(G) such that S₁≠ S₂and |S₁|, |S₂| ≤ t, at least one of the conditions of Lemma 6.5, is satisfied.

FIGURE 6.5. Illustration of Lemma 6.5.

Lemma 6.7   Let G be a system with N nodes and S₁, S₂⊂ V(G) be two distinct sets with |S₁|, |S₂| ≤ t and |S₁∩ S₂| = p, where 0 ≤ p ≤ t − 1. If |P(G, S₁ ∪ S₂)| > p, then (S₁, S₂) is a distinguishable pair.

Proof:     Let M(V(G), L) be the comparison scheme of G. If |P (G, S₁∪ S₂) | > p, then there must exist a node u ∈ P (G, S₁∪ S₂) such that u ∉ S₁∩ S₂. This implies that u ∈ (S₁− S₂) ∪ (S₂−S₁). By the definition of the probing set, there exist two nodes v, w ∈V(G) − (S₁∪ S₂) such that (u, v)_w∈L, which satisfies condition 1 of Lemma 6.5 Therefore, (S₁, S₂) is a distinguishable pair.    ■

Lemma 6.8    Suppose that G = (V, E) is a connected graph with order_G(v) ≥ t for each node v in G, where t ≥ 0. If U ⊂ V with |U | ≤ t, then P(G, U) = U.

Proof:   Let u be a node in U. Since order_G(u) ≥ t, the cardinality of the minimum node cover in the order graph G^u = (X^u, Y^u) is also at least t. Clearly, U − {u} is not a node cover of G^ubecause |U − {u}| < t. This implies that there exists an edge (v, w) in Y^usuch that v and w are both in U. Moreover, by the definition of the order graph, (v, w) in Y^uif the comparison (u, v)_w exists. Therefore, u ∈ P (G, U) and P (G, U) = U.    ■

6.3     DIAGNOSABILITY OF (1, 2)-MCNS UNDER PMC MODEL

In this section, we consider the diagnosability of (1, 2)-MCNs under the PMC model. The following properties are useful for our analysis.

Lemma 6.9   Let G = (V, E) be a graph representation of a system, where V represents the processors and E represents their interconnections. Then, d(G) ≤ δ (G) under the PMC model.

Proof:     Let u be a node in G with deg(u) = δ(G). Suppose, by contradiction, that d(G) = δ(G) + 1 > δ(G). We then consider the following two distinct sets F₁ = {u} ∪ N(u) and F₂ = N(u). Clearly, F₁≠ F₂, |F₁|, |F₂| ≤ δ(G) is no edge between V(G) − (F₁∪ F₂) and F₁ΔF₂. According to Lemma 6.2, this contradicts the fact that G is (δ(G) + 1)-diagnosable. Therefore, the result holds.    ■

Lemma 6.10    Let G₁and G₂be two graphs with the same number of nodes N, and let t ≥ 2 be a positive integer. If both G₁and G₂are t-connected and N ≥ t + k, then G(G₁, G₂; PM_k) is (t + k)- connected for k ∈ {1, 2}.

Proof:   Let G = G(G₁, G₂; PM_k). Suppose, by contradiction, that κ(G) ≤ t + k − 1. Then, there exists a set U ⊂ V(G) with |U| ≤ t + k − 1 such that G – U disconnected. Let U₁ = U ∩ V(G₁), U₂ = U ∪ V(G₂), n₁ = |U₁|, and n₂ = |U₂|. Without loss of generality, we assume that n₁≥ n₂and consider the following cases.  ■

Case 1: n₁< t and n₂< t. Since κ(G_i) ≥ t > n₁≥ n₂for i ∈ {1, 2}, both G₁− U₁and G₂− U₂are connected. Since G − U is disconnected, each edge (u, v) ∈ PM_k must have u ∈ U or v ∈ U. Otherwise, if there is an edge (u, v) ∈ PM_k with u ∉ U and v ∉ U, then G − U could be connected by connecting the connected components of G₁− U₁and G₂− U₂via (u, v), which would be a contradiction. Moreover, because each node in G_i for i ∈ {1, 2} is incident to exactly k edges in PM_k, |U| ≥ N ≥ t + k, but this contradicts the assumption that |U| ≤ t + k − 1.

Case 2: n₁ = t and n₂≤ k − 1 ≤ 1. Since n₂≤ k − 1 and each node in G is incident to exactly k edges in PM_k, each node u in G₁− U₁ has at least one neighbor in G₂− U₂. Moreover, since G₂is t-connected and n₂ = k − 1 ≤ 1 < 2 ≤ t, G₂− U₂is also connected. Therefore, G − U is connected, but this is a contradiction.

Case 3: n₁ = t + 1 and n₂≤ k − 2. Since n₂≥ 0 and k ∈ {1, 2}, we have k = 2. Hence, G is constructed from G₁and G₂by connecting V(G₁) and V(G₂) via two distinct perfect matchings PM₂between V(G₁) and V(G₂). As each node u in G₁− U₁has two neighbors in G₂and n₂ = 0, G − U is connected. This is also a contradiction.

By combining the above cases, we complete the proof. ■

Next, we demonstrate the diagnosability of (1, 2)-MCNs under the PMC model.

Lemma 6.11     Let t ≥ 2 be a positive integer and let G₁and G₂be two graphs with the same number of nodes N, where N ≥ t + 3 . If G₁and G₂are t-connected, then G(G₁, G₂; PM_k) is (t + k)-diagnosable for k ∈ { 1, 2}.

Proof:   We prove this lemma by showing that the condition of Lemma 6.2 holds. Let F1, F₂⊂ V(G) be two distinct sets with |F₁|, |F₂| ≤ t + k for k ∈ {1, 2}; and let |F₁∈ F₂| = p, where 0 ≤ p ≤ t + k − 1.

Since |F₁∪ F₂| = |F₁| + |F₂| − |F₁| ∪ |F₂|, |F₁∪ F₂| ≤ 2(t + k) − p; hence, we have|F1∪ F₂| ≤ 2(t + k). Moreover, because |V (G₁)| = |V (G₂)| = N ≥ t + 3, |V (G) − (t + k) = 6 − 2 k ∈ {2, 4} for k ∈ {1, 2}, so at least two nodes must be in G − (F₁∪ F₂). Furthermore, |F₁Δ F₂| ≠ 0 because F₁and F₂are two distinct sets. On the other hand, since G₁and G₂are t-connected, then by Lemma 6.10, G(G₁, G₂; PM_k) is (t + k)-connected for k ∈ {1, 2}. This means G – (F₁∩ F₂) is also connected because 0 ≤ p ≤ t + k - 1. therefore, there must exist a path in G – (F₁∩ F₂)that joins a node in V(G) − (F₁∪ F₂) to a node in F₁ΔF₂, which implies that an edge (u, v) exists, where u ∈ V(G) − (F₁∪ F₂) and v ∈ F₁ΔF₂. By Lemma 6.2, G is (t + k)-diagnosable.    ■

Lemma 6.12   Let t ≥ 2 be a positive integer and let G₁ and G₂be two graphs with the same number of nodes N. If G₁and G₂are t-diagnosable and t-connected, then a (1, 2)-MCN G(G₁, G₂; PM_k) is (t + k)-diagnosable for k ∈ {1, 2 }.

Proof:    We prove this lemma by showing that the two conditions of Lemma 6.3 hold. Since G₁and G₂are t-diagnosable, then by condition 1 of Lemma 6.4, we have N ≥ 2 t + 1. Moreover, the number of nodes in G is equal to 2 N ≥ 2(2 t + 1) > 2(t + k) + 1 for k ∈ {1, 2} and t ≥ 2. Therefore, condition 1 of Lemma 6.3 holds.

On the other hand, since G₁and G₂are both t-connected, then by Lemma 6.10, G(G₁, G₂; PM_k) is (t + k)-connected for k ∈ {1, 2}; that is, κ(G(G₁, G₂; PM_k)) ≥ t + k. Therefore, condition 2 of Lemma 6.3 holds. Because both conditions of Lemma 6.3 hold, G(G₁, G₂; PM_k) is (t + k)-diagnosable for k ∈ {1, 2}.       ■

6.4   DIAGNOSABILITY OF 2-MCNs UNDER MM* MODEL

In this section, we study the diagnosability of 2-MCNs under the MM* model. Some useful properties are shown as follows.

Lemma 6.13     Let G = (V, E) be a graph representation of a system, where V represents the processors and E represents their interconnections. Then, d(G) ≤ δ(G) under the MM* model.

Proof:    Suppose, by contradiction, that G is (δ(G) + 1)-diagnosable. Let u be an arbitrary node in G, and let F₁ = {u} ⋃ N(u) and F₂ = N(u). Clearly, F₁≠ F₂, N(u) = F₁⋂ F₂, and |F₁|, |F₂| ≤ δ(G) + 1. However, node u cannot be compared by any other node in V(G) − F₁− F₂, which implies that none of the conditions in Lemma 6.5, is satisfied. This is contrary to that G is (δ(G) + 1)-diagnosable, which leads to that d(G) ≤ δ(G), the result holds.    ■

Lemma 6.14    Let G₁and G₂be two networks with the same number of nodes N, and let t ≥ 2 be a positive integer. If order_Gi(v) ≥ t for each node v in G_i, where i = 1, 2, then order_G(v)≥ t + 2 for each node v in G(G₁, G₂; PM₂).

Proof:    For convenience, let G = G(G₁, G₂;PM₂). Let v be an arbitrary node of G. Without loss of generality, we assume that v ∈ V (G₁), and let u and w be two v's neighbors in G₂, where (v, u), (v, w) ∈ PM₂. Recall that G^v₁and G^vdenote the order graphs of v for G₁and G, respectively. Because G^v₁is a subgraph of G^v, every node cover of G^vcontains a node cover of G^v₁. Moreover, since each node in G₂has the order t ≥ 2, the cardinality of a minimum node cover of G^u₂(respectively, G^w₂ ) is at least 2, which implies that |N_G2(u)|≥2 (respectively, |N_G2(w)|≥2) because N_G2(u) (respectively, N_G2 (w)) forms a node cover of G^u₂. (respectively, G^w₂.). Let u′, u′′∈N_G2(u) and w′, w′′∈N_G2(w). Then, we have the following possible cases: (1) |{u′, u″} ⋂{w′, w″}| = 2, that is, u′ and u′′ (w′ and w′′) are both common neighbors of u and w(see Fig. 6.6a); (2) |{u′, u″}⋂{w′, w″} = 1, that is, uand w have exactly one common neighbor (see Fig. 6.6b); (3)|{u ′, u″}⋂{w′, w″}| = 0, that is, u and w have no common neighbor (see Fig. 6.6c). In each of the above cases, at least two nodes must be included into a node cover to cover edges (u, u′), (u, u″), (w, w′), and (w, w′′).

Since edges (u, u′), (u, u″), (w, w′), and (w, w″)belong to E(G^v)–E(G^v₁) and every node cover of G^v contains a node cover of (G^v₁), order _G(v) ≥ order_G1(v) + 2 ≥ t + 2.

Now, we are ready to state and prove the following theorem about the diagnosability of 2-MCNs under the MM* model.

FIGURE 6.6. Illustration of the proof of Lemma 6.14

Theorem 6.1  Let t ≥ 2 be a positive integer and let G₁ and G₂ be two graphs with the same number of nodes N, where N ≥ t + 3. If order_Gi (v) ≥ t, κ(G_i) ≥ t, and |NG_i (v)|≥ 3 for each node v ∈ V(G_i), where i = 1, 2, then G(G₁, G₂; PM₂) is (t + 2 )-diagnosable.

Proof:   For convenience, let G = G(G₁, G₂; PM₂). Let S₁, S₂⊂ V(G) be two distinct sets with |S₁|, |S₂| ≤ t + 2 and let |S₁∩ S₂| = p, where 0 ≤ p ≤ t + 1. Also, let S_Gi = V(G_i) ⋂ (S₁⋃ S₂) for i = 1, 2 with |S_G1| = n₁ and |S_G2| = n₂. Clearly, n₁ + n₂≤ 2(t + 2) − p. Without loss of generality, we assume that n₁≤ n₂. Since

the maximum value of n₁is equal to t + 2 when p = 0 and n₁ = t + 2. We divide the proof into two cases, according to the combined values of n₁, n₂, and t. The first case is n₂ ≤ t, which implies n₁≤ t. The second case is n₂> t, and this case is further divided into three subcases: n₁< t, n₁ = t, and n₁> t. For simplicity, we say that a comparison (u, v)_w is good if it satisfies condition 1 of Lemma 6.5.

Case 1: n₂≤ t, and this implies n₁≤ t. By Lemma 6.8, P(G₁, S_G1) = S_G1 and P(G₂, S_G2) = S_G2. Then, Therefore, by Lemma 6.7, (S₁, S₂) is a distinguishable pair.

Case 2: n₂> t. We have the following scenarios.

Case 2.1: n₁< t. This implies n₂> n₁.

Case 2.1.1: n₂> p. By Lemma 6.8, Moreover, since each node in S_G2is adjacent to exactly two nodes in G₁(via PM₂) and n₂> n₁, S_G2contains a set R with |R | ≥ n₂− n₁such that each node in R is adjacent to some node in V (G₁) −S_G1. Let u ∈ R be an arbitrary node and let w be a node in V(G₁) −S_G1adjacent to u. Since κ (G₁) ≥ t and is connected, which implies that there is another node v ∈ V (G₁) − S_G1 adjacent to w. Clearly, (u, v)_w is a comparison. By combining the above arguments, we have Therefore, by Lemma 6.7, (S₁, S₂) is a distinguishable pair.

Case 2.1.2: n₂ = p. In this case, from n₂≥ t + 1 and p ≤ t + 1, this implies n₂ = p = t + 1; from n₁ + n₂≤ 2(t + 2) − p, it follows n₁≤ 2; and also, n₁> 0 from n₂ = p and S₁, S₂are distinct. Thus, . We have the following scenarios.

Case 2.1.2.1: . Let u be such a node in . Since n₁≤ 2 and |N_G1(u)| ≥ 3 by the hypothesis, there exists a node w ∈ V(G₁) − S_G1 adjacent to u. Moreover, because n₁< t and κ(G₁) ≥ t, is connected, which implies that there is another node v ∈ V(G₁) − S_G1 adjacent to w (see Fig. 6.7a). Then, comparison (u, v)_w is good. Therefore, (S₁, S₂) is a distinguishable pair.

Case 2.1.2.2: |S_G1– (S₁∩S₂)| = 0. This implies |S_G2– (S₁∩S₂)| = n₂ –(p – n₁) = n₁, as p = n₂ and S_G1 ∩ S_G2 = Ø.

Case 2.1.2.2.1: n₁ = 1, which implies that there is exactly one node in S_G2– (S₁∩S₂). Let x be the node in S_G2– (S₁∩S₂). Since n₁ = 1, there exists at least one node adjacent to x via PM₂(see Fig. 6.7b). Then, the result that (S₁, S₂) is a distinguishable pair can be shown using a similar argument to that presented in Case 2.1.2.1.

Case 2.1.2.2.2: n₁ = 2; that is, |S_G2– (S₁∩S₂)| = 2 (note that this case does not occur when t = 2, as n₁< t). Let {x, y} = S_G2– (S₁∩S₂). If at least one node in {x, y} is adjacent to some node (see Fig. 6.7c), then the result that (S₁, S₂) is a distinguishable pair can be shown using a similar argument to that presented in Case 2.1.2.1.

Otherwise, edges in PM₂that are incident to the nodes in {x, y} are also incident to the node in S_G1 and vice versa (recall that (see Fig. 6.7d). This implies that the nodes in cannot be adjacent to nodes in S_G1 via PM₂. Thus, every node must be adjacent to some node via PM. Since and G₂is t-connected. {x, y})] is connected. Hence, at least one node in {x, y}, say, y, must be adjacent to some node and, in turn, z must be adjacent to some node Thus, comparison (y, z′) _z is good, and (S₁, S₂) is a distinguishable pair.

Case 2.2: n₁ = t. Since n₂≥ t + 1 and n₁ + n₂ ≤ 2(t + 2) − p, we have p ≤ 3. We have the following scenarios.

Case 2.2.1: p ≤ t.

Case 2.2.1.1: . By the assumption of this case and contains at least one node. Then, by an argument similar to the one used in Case 2.1.2.1, we can show that (S₁, S₂) is a distinguishable pair.

Case 2.2.1.2: This implies and sets V (G₂) ∈ S₁and V (G₂) ∈ S₂are disjoint. If there exists at least one isolated node in let w be one such node. Since w is adjacent to three nodes in S_G2and to at least two nodes in either (S₁− S₂) or (S₂− S₁), which implies that condition 2 or 3 of Lemma 6.5 holds (see Fig. 6.8a). Therefore, (S₁, S₂) is a distinguishable pair.

Otherwise, given that G₂is connected, there exists a node u in either , which is adjacent to some node w in Since w is not an isolated node in, w must be adjacent to some node v also in , which implies that (u, v)_w is good (see Fig. 6.8b). Therefore, (S₁, S₂) is a distinguishable pair.

Case 2.2.2: p > t. Note that this case occurs only when t = 2, as p ≤ 3. Thus, n₁ = 2, p = 3, and n₂ = 3.

Case 2.2.2.1: ; that is, contains at least one node. Then, the result that (S₁, S₂) is a distinguishable pair can be shown using an argument similar to that presented in Case 2.1.2.1.

Case 2.2.2.2: ; this implies that there are exactly two nodes in Then, the result that (S₁, S₂) is a distinguishable pair can be shown using an argument similar to that presented in Case 2.1.2.2.2.

Case 2.3: n₁> t; thus, n₂≥ n₁> t. Moreover, since n₁ + n₂≤ 2(t + 2) – p, we have p ≤ 2. There are the following scenarios.

Case 2.3.1: p = 0; this implies S₁∪ S₂ = (S₁− S₂) ∪ (S₁− S₂). By using an argument similar to that presented in Case 2.2.1.2, we can show that (S₁, S₂) is a distinguishable pair.

Case 2.3.2: p > 0. We first consider the situation where every connected component in G [ V (G) − S₁− S₂] contains at least two nodes. Since p = |S₁∩ S₂| ≤ 2 and κ (G) ≥ t + 2 ≥ 4 for t ≥ 2 (according to Lemma 6.10,)n, G −(S₁∩ S₂) is connected. Hence, there exists a node u ∈ (S₁− S₂) ∪ (S₂− S₁) adjacent to some node w, which belongs to a component C in G [ V (G) − S₁− S₂]. Since |V (C) | ≥ 2, there is a node v ∈ C adjacent to w. Then, (u, v)_w is good, and thus, (S₁, S₂) is a distinguishable pair (see Fig. 6.9a).

Otherwise, every connected component G[V(G) − S₁− S₂] is an isolated node. Let w be an arbitrary isolated node in G[V(G) − S₁− S₂]. Since |N_Gi(v)| ≥ 3for every node v ∈ V (G_i), we have |N_G(w)| ≥ 5. Moreover, because p ≤ 2, v is adjacent to at least two nodes in S₁− S₂or S₂− S₁, which implies that condition 2 or 3 of Lemma 6.5, holds (see Fig. 6.9b). Therefore, (S₁, S₂) is a distinguishable pair.

By combining the above cases, we complete the proof.    ■

Figure 6.10a illustrates a 2-MCN G = G(G₁, G₂;PM₂) with order_Gi (v) = 3, κ (G_i) = 3, and for each node v in G_i, where i = 1, 2. By Theorem 6.1, G is 5-diagnosable 2-MCN. Figure 6.10b illustrates a 2-MCN G = G(G₁, G₂; PM₂) with order _Gi(v) = 2, κ (G_i) = 2, and |NG_i (v)| ≥ 2 for each node v in G_i, where i = 1, 2. Since G does not satisfy the condition where |NG_i(v)| ≥ 3 in Theorem 6.1, it is not 4-diagnosable. Let S₁ = {u₃, u₄, u₅, v₄} and S₂ = {u₄, v₃, v₄, v₅} with S₁∈ S₂ = {u₄, v₄}. Clearly, none of the nodes in (S₁− S₂) ∪ (S₂− S₁) = {u₃, v₃, u₅, v₅} can be compared by another two nodes in V(G) − (S₁∪ S₂) = {u₁, v₁, u₂, v₂}. By Lemma 6.5 and 6.6, G is not 4-diagnosable.

Corollary 6.1   Let t ≥ 3 be a positive integer and let G₁and G₂be two graphs with the same number of nodes N, where N ≥ t + 3. If order_Gi(v) ≥ t and κ (G_i) ≥ t for i = 1, 2, then G(G₁, G₂; PM₂) is (t + 2 )-diagnosable.

FIGURE 6.7. Illustration of Case 2.3.2 in the proof of Theorem 6.1.

FIGURE 6.8. Illustration of Case 2.2.1.2 in the proof of Theorem 6.1.

FIGURE 6.9. Illustration of Case 2.3.2 in the proof of Theorem 6.1.

FIGURE 6.10. Two 2-MCNs for illustrating the usage of Theorem 6.1: (a) a 5-diagnosable 2-MCN and (b) a non-4-diagnosable 2-MCN, where the white, gray, and black nodes belong to S₁ ∩ S₂, (S₁ – S₂) ⋃ (S₂ – S₁), andV(G)–(S₁⋃ S₂) respectively.

6.5   APPLICATION TO MULTIPROCESSOR SYSTEMS

In this section, we apply the lemmas derived in Section 6.3 and 6.4 to several popular multiprocessor systems. Of course, they can also be applied to many other potentially useful systems.

6.5.1  The Diagnosability of Hypercubes

An n-dimensional hypercube Q_n has 2ⁿnodes and can be defined recursively as follows. Q₁is a complete graph with two nodes labeled 0 and 1, respectively. For n ≥ 2, Q_n consists of two Q_{n− 1}s, denoted by and , respectively. In addition, there exists a perfect matching PM₁between and so that node is connected to node if and only if u_i = v_i for 0 ≤ i ≤ n – 2. Figure 6.11 illustrates Q₃and Q₄.

FIGURE 6.11. Q₃and Q₄.

FIGURE 6.12. CQ₃and CQ₄.

Lemma 6.15  Q_n is n-diagnosable for n ≥ 5 under the PMC model.

Proof:  By the definition of hypercubes, Since Q_n is n-connected for n ≥ 3 [30] and for n ≥ 4, then by Lemma 6.11, Q_n is n-diagnosable for n ≥ 5.   ■

Theorem 6.2  d(Q_n) = n for n ≥ 5 under the PMC model.

Proof: By Lemma 6.15, d(Q_n) ≥ n for n ≥ 5. Moreover, since Q_n for n ≥ 1 is a regular graph with a common degree n, that is, δ(Q_n) = n, then by Lemma 6.9, d(Q_n) ≤ δ(Q_n) = n. Hence, d(Q_n) = n for n ≥ 5.   ■

6.5.2   The Diagnosability of Crossed Cubes

An n-dimensional crossed cube CQ_n [31] has 2ⁿnodes and can be defined recursively as follows. CQ₁is a complete graph with two nodes labeled 0 and 1, respectively. For cases where n ≥ 2, CQ_n consists of two CQ_n−1s, denoted by and , respectively. In addition, there exists a perfect matching PM₁between and so that is connected to node if and only if (1) u_n−2 = v_{n− 2}if n is even; and (2) , for

Figure 6.12 illustrates CQ₃and CQ₄.

Lemma 6.16  CQ_n is n-diagnosable for n ≥ 5 under the PMC model.

Proof:   By the definition of crossed cubes, . Moreover, since a CQ_n is n-connected for n ≥ 3 [32], and therefore, by Lemma 6.11, CQ_n is n-diagnosable for n ≥ 5.   ■

Theorem 6.3   d(CQ_n) = n for n ≥ 5 under the PMC model.

Proof:   By Lemma 6.16, d(CQ_n) ≥ n for n ≥ 5. Since CQ_n for n ≥ 1 is a regular graph with a common degree n, that is, δ(CQ_n) = n, then, by Lemma 6.9, d(CQ_n) ≤ δ(CQ_n) = n. Hence, d(CQ_n) = n for n ≥ 5.   ■

6.5.3   The Diagnosability of Möbius Cubes

For a binary bit x, let be one's complement of x, that is, = 1 iff x = 0, and = 0 iff x = 1. An n-dimensional 0-Möbius cube 0-MQ_n (respectively, 1-Möbius cube 1-MQ_n) [33] has 2ⁿnodes, and can be recursively defined as follows. 0-MQ₁(respectively, 1-MQ₁) is a complete graph with two nodes labeled 0 and 1, respectively. 0-MQ2is a graph with V (0-MQ₂) = {00, 01, 10, 11} and E (0-MQ₂) = {(00, 01), (00, 10), (01, 11), (10, 11)}. 1-MQ₂is a graph with V (1-MQ₂) = {00, 01, 10, 11} and E (1 -MQ2) = {(00, 01), (00, 11), (01, 10)}, (10, 11)}. For n ≥ 3, 0-MQ_n (respectively, 1-MQ_n) consists of 0-MQ_{n −1}and 1-MQ_n−1, and there is a perfect matching PM₁ between V(0-MQ_n−1) = {0u_n−2u_n−3…u₀|u_i∈ {0, 1}} and V(1-MQ_{n −1}) = {1 v_n−2v_{n −3}…v₀|v_i∈ {0, 1}} so that node u = 0 u_n−2u_n−3…u₀∈ V(0-MQ_{n− 1}) is connected to node v = 1v_n−2v_n−3…v₀∈ V(1-MQ_n−1) in 0-MQ_n(respectively, 1-MQ_n) if and only if u_i = v_i(respectively, u_i = ) for all 0 ≤ i ≤ n − 2. Figure 6.13 illustrates MQ₃and MQ₄.

Lemma 6.17  MQ_n is n-diagnosable for n ≥ 5 under the PMC model

Proof:   By the definition of M ö bius cubes, MQ_n = G(0-MQ_n−1, 1-MQ_n−1; Moreover, an MQ_n is n-connected for n ≥ 3 [9], and |V (0-MQ_{n − 1})| = |V (1-MQ_{n − 1})| = 2 n⁻¹≥ (n − 1) + 3 = n + 2 for n ≥ 4; therefore, by Lemma 6.11, MQ_n is n -diagnosable for n ≥ 5.    ■

Theorem 6.4   d(MQ_n) = n for n ≥ 5 under the PMC model.

Proof:   By Lemma 6.17, d(MQ_n) ≥ n for n ≥ 5. Since MQ_n for n ≥ 1 is a regular graphwith a common degree n, that is, δ(MQ_n) = n, then by Lemma 6.9, d(MQ_n) ≤ δ(MQ_n) = n. Hence, d(MQ_n) = n for n ≥ 5.   ■

6.5.4   The Diagnosability of Twisted Cubes

An isomorphism from a simple graph G to a simple graph H is a one to one and onto function π: V(G) → V(H) such that (u, v) ∈ E(G) if and only if (π(u), π(v)) ∈ E(H). We say “G, written as G≅ H, is isomorphic to H” if there is an isomorphism from G to H. Given a binary string u = u_n−1u_n−2…u₀for u_i∈ {0, 1},

let P_i(u) = u_i·u_i−1·…·u₀, where · represents an exclusive-or operation. An n -dimensional twisted cube TQ_n [34] for an odd integer n has 2ⁿnodes, and can be defined recursively as follows. TQ₁is a complete graph with two nodes labeled 0 and 1, respectively. For an odd integer n ≥ 3, TQ_n is decomposed into four sets: and where for (i, j) ∈ {(0, 0), (0, 1), (1, 0), (1, 1)}}. Note that the subgraph induced by in TQ_n is isomorphic to TQ_n−2. Moreover, node u_n−1u_n−2u_n−3…u₀is connected to nodes and and respectively) if and only if P_n−3(u) = 0 (respectively, P_n−3(u) = 1). Figure 6.14 illustrates TQ₃and TQ₅.

Based on the above definition, TQ_n is composed of four TQ_n−2's, which are subgraphs induced, respectively, by and where n ≥ 3 is an odd integer. Let S₀and S₁be two subgraphs of TQ_n induced by and respectively. In fact, and . Moreover, each node u = u_n−1u_n−2u_n−3…u₁u₀∈ S₀is connected to if P_n−3(u) = 0 and to if P_n−3(u) = 1. It is not difficult to see that each node u ∈ S₀has exactly one neighbor v in S₁. Therefore, the edges between S₁ and S₂in TQ_n form a perfect matching; that is, TQ_n = G(S₀, S₁; PM₁).

FIGURE 6.13. MQ₃ and MQ

FIGURE 6.14. TQ₃ and TQ5.

Lemma 6.18  Let for j = 0, 1. Then, S_j is (n − 1)-connected for n ≥ 4.

Proof: SinceTQ_n is n - connected for n ≥ 3 [35], then by Lemma 6.10, S_j is (n − 1)-connected for n ≥ 4.   ■

Lemma 6.19  TQ_n is n-diagnosable for n ≥ 5 under the PMC model.

Proof:   By the definition of twisted cubes, TQ_n = G(S₀, S₁;PM₁). Moreover, by Lemma 6.18, for j = 0, 1 is (n − 1)-connected for n ≥ 4, and for n ≥ 4; therefore, by Lemma 6.11, TQ_n is n-diagnosable for ≥ 5.   ■

Theorem 6.5    d(TQ_n) = n for n ≥ 5 under the PMC model.

Proof:   By Lemma 6.19, d(TQ_n) ≥ n for n ≥ 5. Since TQ_n for n ≥ 1 is a regular graph with a common degree n, that is, δ(TQ_n) = n, then by Lemma 6.9, d(TQ_n) ≤ δ(TQ_n) = n. Hence, d(TQ_n) = n for n ≥ 5.   ■

6.5.5    The Diagnosability of Locally Twisted Cubes

An n - dimensional locally twisted cube LTQ_n [36] has 2ⁿ nodes and can be defined recursively as follows. LTQ₁ is a complete graph with two nodes labeled 0 and 1, respectively.LTQ₂ is a graph with V(LTQ₂) = {00, 01, 10, 11} and E(LTQ₂) = {(00, 01), (01, 11)}, (11, 10), (10, 00)}. For n ≥ 3, LTQ_n consists of two LTQ_n−1, denoted by and , respectively. In addition, there is a perfect matching PM₁ between and such that node is connected to node, where “ " denotes a “mod 2” operation. Figure 6.15 illustrates LTQ₃ and LTQ₄.

Lemma 6.20  LTQ_n is n-diagnosable for n ≥ 5under the PMC model.

Proof:   By the definition of locally twisted cubes, . Moreover, since an LTQ_n isn-connected for n ≥ 3 [36] and for n ≥ 4, then, by Lemma 6.11, LTQ_n is n-diagnosable for n ≥ 5.   ■

Theorem 6.6    d(LTQ_n) = n for n ≥ 5 under the PMC model.

Proof: By Lemma 6.20, d(LTQ_n) ≥ n for n ≥ 5. Since LTQ_n for n ≥ 1 is a regular graph with a common degree n, that is, δ(LTQ_n) = n, then, by Lemma 6.9, d(LTQ_n) ≤ δ(LTQ_n) = n. Hence, d(LTQ_n) = n for n≥ 5.   ■

6.5.6   The Diagnosability of Generalized Cubes

Two edges in a graph G are said to be independent if they do not share a common node. Given two independent edges, (x, y) and (u, v) in E(G), an X-change operation on (x, y) and (u, v), denoted by X[(x, y), (u, v)], would replace the two edges (x, y) and (u, v) with two new edges, (x, v) and (y, u), as shown in Figure 6.16. Note that an X-change operation preserves the degree of the graph.

An n-dimensional generalized twisted cube GQ_n [37] has 2ⁿ nodes and can be defined as follows. GQ₀ is a single node. GQ₁ is a complete graph with two nodes labeled 0 and 1, respectively. GQ₂ is a graph with V(GQ₂) = {00, 01, 10, 11} and E(GQ₂) = {(00, 01), (01, 11), (11, 10), (10, 00)}. For n ≥ 3, GQ_n = TQ₃×GQ_n-3, where × is the Cartesian product of two graphs. Alternatively, GQ_n can be represented by K₂×GQ_n−1 if mod(n, 3) = 1 or 2, and K₂ ⊙ GQ_n−1if mod(n, 3) = 0, where ⊙ indicates that the Cartesian product operation is followed by the X-change operations X[010b_n−4b_{n− 5}…b₀, 110b_n−4b_n−5…b₀), (011b_n−4b_n−5…b₀, 111b_n−4b_n−5…b₀)], where b_n−4b_n−5…b₀ ∈ {0, 1}ⁿ⁻³ [37]. Based on the above definition, GQ_n belongs to the class of (1, 2)-MCNs and is isomorphic to G(GQ_n−1, GQ_n−1; PM). Figure 6.17 illustrates GQ₃ and GQ₄.

Lemma 6.21  GQ_n is n-diagnosable for n ≥ 5 under the PMC model.

Proof:   By the definition of generalized twisted cubes, GQ _n ≅ G (GQ _{n− 1}, GQ_n−1; PM₁). Moreover, a GQ _n is n-connected for n ≥ 3 [38], and |V(GQ_n−1)| = |V(GQ_n−1)| = 2ⁿ⁻¹ ≥ (n − 1) + 3 = n + 2 for n ≥ 4; therefore, by Lemma 6.11, GQ_n is n-diagnosable for n ≥ 5.   ■

Theorem 6.7  d(GQ_n) = n for n ≥ 5 under the PMC model.

Proof:   By Lemma 6.21, d(GQ_n) ≥ n for n ≥ 5. Since GQ_n for n ≥ 1 is a regular graph with a common degree n, that is, δ(GQ_n) = n, then, by Lemma 6.9, d(GQ_n) ≤ δ(GQ_n) = n. Hence, d(GQ_n) = n for n ≥ 5.   ■

FIGURE 6.15. TQ₃ and LTQ₄.

FIGURE 6.16. An X-change operation.

FIGURE 6.17. GQ₃ and GQ₄.

6.5.7  The Diagnosability of a Recursive Circulant

A recursive circulant [39, 40] G(N, d) for d ≥ 2 is defined as follows: The node set V = {v₀, v₁, v₂,…,v_N−1} and the edge set E = {(v_i, v_j)| there exists k for 0 ≤ k ≤ ⌈log _dN⌉ − 1 such that i + d^k ≡ j(mod N)}. In fact, G(N, d) is a circulant graph [41] with N nodes and jumps to the power of d, that is, d⁰, d¹, d²,…,d^{⌈log_d N⌉−1}. Recursive circulant G(N, d) has a recursive structure when N = cdⁿ for 1 ≤ c < d.G (cdⁿ, d) for n ≥ 1 can be constructed recursively on d copies of G(cdⁿ⁻¹, d) as follows: Let G_i = (V_i, E_i) for 0 ≤ i ≤ d − 1 be a copy of G(cdⁿ⁻¹, d) with , where G_i is isomorphic to G(cdⁿ⁻¹, d) by the isomorphism mapping v_jⁱ to v_j. We can relabel v_jⁱ as v_{jd + i}. The node set V of G(cdⁿ, d) is , and the edges set E is , where X = {(v_j, v_j′)|j + 1 ≡ j′ (mod cdⁿ)}. In this chapter, we focus G(N, d) with N = 2ⁿ and d = 4. In the recursive structure, G(2ⁿ, 4) consists of four components: G₀, G₁, G₂, and G₃, each of which is isomorphic to G(2ⁿ⁻², 4). Figure 6.18 illustrates G(2³, 4) and G(2⁵, 4).

Let H₀ and H₁ be two subgraphs of G(2ⁿ, 4) induced by V(G₀) ∪ V(G₁) and V(G₂) ∪ V(G₃), respectively, where G_i ∈ G(2ⁿ⁻², 4) for i ∈ {0, 1, 2, 3}. In fact, H₀ = (G₀, G₁; PM₁) and H₁ = (G₂, G₃; PM₁). Moreover, it is not difficult to see that each node u ∈ H₀ has exactly one neighbor v in H₁. Therefore, the edges between S₁ and S₂ in G(2ⁿ, 4) form a perfect matching; that is, G(2ⁿ, 4) = (H₀, H₁; PM₁).

Lemma 6.22   Let H₀ and H₁ be two subgraphs of (G₀, G₁; PM₁) and (G₂, G₃;PM₁), respectively, where G_i∈ G(2ⁿ⁻², 4) for i ∈ { 0, 1, 2, 3 }. Then, H₀ and H₁ are (n−1)-connected for n ≥ 4.

Proof:   Since G(2ⁿ, 4) is n-connected for n ≥ 3 [42], then, by Lemma 6.10, H₀ and H₁ are (n − 1)-connected for n ≥ 4.   ■

Lemma 6.23  G(2ⁿ, 4) is n-diagnosable for n ≥ 5 under the PMC model.

Proof:   By the definition of recursive circulants G(2ⁿ, 4), G(2ⁿ, 4) = G(H₀, H₁; PM₁). Moreover, by Lemma 6.22, H₀ = G₀, G₁;PM₁)and H₁ = (G₀, G₃;PM₁) are (n − 1)-connected for n ≥ 4, and ∣V (H₀)∣ = ∣V (H₁)∣ = 2ⁿ⁻¹ ≥ (n − 1) + 3 = n + 2 for n ≥ 4; therefore, by Lemma 6.11, G(2ⁿ, 4) is n-diagnosable for n ≥ 5.   ■

Theorem 6.8    d(G(2ⁿ, 4)) = n for n ≥ 5 under the PMC model.

Proof: By Lemma 6.23, d(G(2ⁿ, 4)) ≥ n for n ≥ 5. Since G(2ⁿ, 4) for n ≥ 3 is a regular graph with a common degree n, that is, δ(G(2ⁿ, 4)) = n, then, by Lemma 6.9, d(G(2ⁿ, 4)) ≤ δ(G(2 ⁿ, 4)) = n. Hence, d(G(2ⁿ, 4)) = n for n ≥ 5.   ■

FIGURE 6.18.  G(2³, 4) and G(2⁵, 4).

6.5.8   The Diagnosability of Hyper-Petersen Networks

The Petersen graph P is a simple graph in which the nodes are two-element subsets of a five-element set and the edges are pairs of disjoint two-element subsets. An n-dimensional hyper-Petersen network [43], denoted by HP _n forn ≥ 3, has HP_n ≅Q_n−3 × P. Alternatively, HP_n ≅HP_n−1 × K₂, where n ≥ 4; that is, HP_n ≅ G(HP_n−1, HP_n−1; PM₁). Figure 6.19 illustrates HP₃ and HP₄. Note that HP_n is a regular graph with 1.25(2ⁿ) nodes that have a common degree n.

Lemma 6.24  HP_n is n-diagnosable for n ≥ 4 under the PMC model.

Proof: By the definition of hyper-Petersen networks, HP_n ≅ G(HP_n−1, HP_n−1;PM₁). Moreover, HP_n is n-connected for n ≥ 3 [44], and ∣V(HP_n−1)∣ = ∣V (HP_n−1) ∣ = 1.25

(2^{+ 1}) ≥ (n − 1) + 3 = n + 2 for n ≥ 3; therefore, by Lemma 6.11, HP_n is n-diagnosable for n ≥ 4.   ■

Theorem 6.9   d(HP_n) = n for n ≥ 4 under the PMC model.

Proof: By Lemma 6.24, d (HP _n)≥ n for n ≥ 4. Since HP _n for n ≥ 3 is a regular graph with a common degree n, that is, δ(HP_n) = n, then, by Lemma 6.9, d(HP_n) ≤ δ(HP_n) = n. Hence, d(HP_n) = n for n ≥ 4.       ■.

FIGURE 6.19. HP₃ and HP₄.

6.5.9   The Diagnosability of Folded Hypercubes

An n-dimensional folded hypercube [45], denoted by FQ_n, is a regular n-dimensional hypercube augmented by adding more edges between its nodes. More specifically, FQ_n has 2ⁿ nodes and can be defined as follows. FQ₁ is a complete graph with two nodes labeled 0 and 1, respectively. For n ≥ 2, there exists a PM₂ between in such a way that node is connected to node if and only if one of the following conditions hold: (1)u_i = v_i for 0 ≤ i ≤ n − 2 (called a hypercube edge), or (2) for 0 ≤ i ≤ n − 2(called a complementary edge) (Fig. 6.20).

Lemma 6.25   FQ_n is (n + 1)- diagnosable for n ≥ 5 under the PMC model.

Proof: By the definition of folded hypercubes, . Moreover, a Q_n is n-connected for n ≥ 3 [30], and for n ≥ 4; therefore, by Lemma 6.11 , FQ _n is (n + 1)-diagnosable for n ≥ 5.      ■

Theorem 6.10   d(FQ_n) = n + 1 for n ≥ 5 under the PMC model.

Proof: By Lemma 6.25, d(FQ_n) ≥ n for n ≥ 5. Since FQ_n for n ≥ 1 is a regular graph with a common degree n + 1, that is, δ(FQ_n) = n + 1, then, by Lemma 6.9, d(FQ_n) ≤ δ(FQ_n) = n + 1. Hence, d(FQ_n) = n + 1 for n ≥ 5.    ■

Lemma 6.26  FQ_n is (n + 1)-diagnosable for n ≥ 4 under the MM^* model.

Proof:   By the definition, FQ_n is obtained by connecting two (n − 1)- dimensional hypercubes via PM₂; that is, . Since an n-dimensional hypercube is n-connected and the order of each node equals n [24] for n ≥ 3, then, by Corollary 6.1, FQ_n is (n − 1) + 2 = (n + 1)-diagnosable for n ≥ 4.   ■

Theorem 6.11  d(FQ_n) = n + 1 for n ≥ 4 under the MM^* model.

Proof:   By Lemma 6.26, d(FQ_n) ≥ n + 1 for n ≥ 4. Next, we show that d(FQ_n) ≤ n + 1. Since FQ_n for n ≥ 1 is a regular graph with a common degree n + 1, that is, δ(FQ_n) = n + 1, then, by Lemma 6.13, d(FQ_n) ≤ δ(FQ_n) ≤ n + 1. Hence, d(FQ_n) = n + 1 for n ≥ 4.      ■

FIGURE 6.20. (a) A three-dimensional folded hypercubeFQ₃, and (b) a four-dimensional folded hypercube FQ₄. The dotted lines represent the complementary edges.

6.5.10   The Diagnosability of Augmented Cubes

The n-dimensional augmented cube AQ_n [46] has 2ⁿ nodes and can be recursively defined as follows. AQ₁ is a complete graph with two nodes labeled 0 and 1, respectively. For n ≥ 2, AQ_n consists of two AQ_n−1's, denoted by and , respectively. In addition, there exists a PM₂ between and in such a way that node u = 0u_n−2u_n−3…u₀ ∈ connected to node if and only if one of the following conditions hold: (1) u_i = v_i for 0 ≤ i ≤ n − 2 (called a hypercube edge), or (2) u_i = (called a complementary edge) for 0 ≤ i ≤ n − 2 (Fig. 6.21).

Lemma 6.27  AQ_n is (2n − 1)-diagnosable for n ≥ 5 under the PMC model.

Proof:   By the definition of augmented cubes, Moreover, an AQn is (2n − 1)-connected for n ≥ 4 [46] and for n ≥ 4; therefore, by Lemma 6.11, AQ_n is (2n − 1)-diagnosable for n ≥ 5.   ■

FIGURE 6.21. A four-dimensional augmented cube AQ₄; the dotted lines represent the complementary edges.

Theorem 6.12  d(AQ_n) = 2n− 1 for n ≥ 5 under the PMC model.

Proof:   By Lemma 6.27, d(AQ_n) ≥ 2n − 1 for n ≥ 5. Since an AQ_n for n ≥ 1 is a regular graph with a common degree 2 n − 1, that is, δ(AQ_n) = 2 n − 1, then, by Lemma 6.9, d(AQ_n) ≤ δ(AQ_n) = 2n − 1. Hence, d(AQ_n) = 2n − 1 for n ≥ 5.       ■

Lemma 6.28  The order of each node v in AQ_n is least 2n-1 for n ≥ 4.

Proof:   We prove this lemma by induction on n. Since AQ_n is node symmetric [ 46], we only need to consider the order graph G⁰⁰⁰⁰ for node 0000 in AQ₄. Figure 6.22b illustrates the order graph G⁰⁰⁰⁰ for AQ₄. It is not difficult to verify that the cardinality of a minimum node cover equals 7( = 2 × 4 − 1) using an exhaustive search. Thus, the base case holds. Assume that the lemma holds for dimension n − 1 for n ≥ 5. Now, we consider AQ_n, which is constructed from two AQ_{n− 1} s via PM₂. By the induction hypothesis, the order of each node in AQ _n−1 is at least 2(n − 1) − 1 = 2n − 3. Therefore, by Lemma 6.14, the order of AQ_n is at least (2n − 3) + 2 = 2n − 1.     ■

FIGURE 6.22. (a) AQ₄ and (b) the order graph G⁰⁰⁰⁰, where the white nodes form a minimum node cover.

Lemma 6.29  AQ_nis (2n-1)-diagnosable for n ≥ 5 under the MM* model.

Proof:   By the definition, AQn is obtained by connecting two (n − 1)-dimensional augmented cubes via PM₂; that is, . By Lemma 6.28, Corollary 6.1, and AQ_n is (2n – 1)-connected [46], AQ_n is (2(n − 1) − 1) + 2) = (2n-1))-diagnosable.      ■

Theorem 6.13  d(AQ _n ) = 2n − 1 for n ≥ 5 under the MM* model.

Proof:   By Lemma 6.29, d(AQ_n) ≥ 2n − 1 for n ≥ 5. We next show that d(AQ_n) ≤ 2n − 1. Since AQ_n for n ≥ 1 is a regular graph with a common degree 2n − 1, that is, δ(AQ_n) = 2n − 1, then, by Lemma 6.13, d(AQ_n) ≤ δ (AQ_n) = 2n − 1. Hence, d(AQn) = 2n − 1 for n ≥ 5.   ■

6.6  CONCLUDING REMARKS

Fault diagnosis in multiprocessor systems has received a great deal of attention since Preparata et al. [19] proposed the concept of system-level diagnosis. In this chapter, we have established sufficient conditions that can be utilized to determine the diagnosability of (1, 2)-MCNs under the PMC model, and the diagnosability of 2-MCNs under the MM^* model. By using the established lemmas, we can successfully compute the diagnosability of hypercubes, crossed cubes, Möbius cubes, twisted cubes, locally twisted cubes, generalized twisted cubes, recursive circulants for odd n, hyper-Petersen networks, folded hypercubes, and augmented cubes under the PMC model. Furthermore, we can also successfully compute the diagnosability of folded hypercubes and augmented cubes under the MM^* model. In the future work, we will apply our strategy to some other classes of networks.

REFERENCES

[1] T. Araki and Y. Shibata, “(t, k)-Diagnosable system: A generalization of the PMC models,” IEEE Transactions on Computers, 52 (7): 971‒975, 2003.

[2] J.R. Armstrong and F.G. Gray, “Fault diagnosis in a Boolean n cube array of multiprocessors,” IEEE Transactions on Computers, 30 (8): 587‒590, 1981.

[3] G.Y. Chang and G.H. Chen, “(t, k)-Diagnosability of multiprocessor systems with applications to grids and tori,” SIAM Journal on Computing, 37 (4): 1280‒1298, 2007.

[4] G.Y. Chang, G.J. Chang, and G.H. Chen, “Diagnosabilites of regular networks,” IEEE Transactions on parallel and Distributed system, 16(4): 314–323, 2005.

[5] G.Y. Chang, G.H. Chen, and G.J. Chang, “(t, k) - Diagnosis for matching composition networks,” IEEE Transactions on Computers, 55 (1): 88‒92, 2006.

[6] G.Y. Chang, G.H. Chen, and G.J. Chang, “(t, k) - Diagnosis for matching composition networks under the MM^* model,” IEEE Transactions on Computers, 56 (1): 73‒79, 2007.

[7] K.Y. Chwa and S.L. Hakimi, “On fault identification in diagnosable systems,”IEEE Transactions on Computers, 30(6): 414‒422, 1981.

[8] A. Das, K. Thulasiraman, and V.K. Agarwal, “Diagnosis of t/(t + 1)-diagnosable systems,” SIAM Journal on Computing, 23(5): 895‒905, 1994.

[9] J. Fan, “Diagnosability of the M ö bius cubes,” IEEE Transactions on Parallel and Distributed Systems, 9(9): 923‒928, 1998.

[10] J. Fan, “Diagnosability of crossed cubes under the two strategies,” Chinese Journal ofIEEE Computers, 21(5): 456‒462, 1998.

[11] J. Fan, “Diagnosability of crossed cubes under the comparison diagnosis model,” Transactions on Parallel and Distributed Systems, 13(7): 687‒692, 2002.

[12] S.L. Hakimi and A.T. Amin, “Characterization of connection assignment of diagnosable systems,” IEEE Transactions on Computers, 23(1): 86‒88, 1974.

[13] S.Y. Hsieh and Y.S. Chen, “Strongly diagnosable systems under the comparison diagnosis model,” IEEE Transactions on Computers, 57(12): 1720‒1725, 2008.

[14] S.Y. Hsieh and Y.S. Chen, “Strongly diagnosable product networks under the comparison diagnosis model,” IEEE Transactions on Computers, 57(6): 721‒732, 2008.

[15] S.Y. Hsieh and T.Y. Chuang, “The strong diagnosability of regular networks and product networks under the PMC model,” IEEE Transactions on Parallel and Distributed Systems, 20(3): 367‒378, 2009.

[16] A. Kavianpour and K.H. Kim, “Diagnosability of hypercubes under the pessimistic one - step diagnosis strategy,” IEEE Transactions on Computers, 40(2): 232‒237, 1991.

[17] J.K. Lee and J.T. Butler, “A characterization of t/s-diagnosability and sequential t-diagnosability in designs,” IEEE Transactions on Computers, 39(10): 1298‒1304, 1990.

[18] J. Maeng and M. Malek, “A comparison connection assignment for self-diagnosis of multiprocessor systems,” in Proceedings of the 11th International Symposium on Fault - Tolerant Computing, pp. 173‒175, 1981.

[19] F.P. Preparata, G. Metze, and R.T. Chien, “On the connection assignment problem of diagnosable systems,” IEEE Transactions on Computers, EC-16: 448‒454, 1967.

[20] A. Sengupta and A. Dahbura, “On self-diagnosable multiprocessor system: Diagnosis by the comparison approach,”IEEE Transactions on Computers, 41(11): 1386‒1396, 1992.

[21] A.K. Somani, “Sequential fault occurrence and reconfiguration in system level diagnosis,” IEEE Transactions on Computers, 39(12): 1472‒1475, 1990.

[22] A.K. Somani, V.K. Agarwal, and D. Avis, “A generalized theory for system level diagnosis,” IEEE Transactions on Computers, 36 (5): 538‒546, 1987.

[23] A.K. Somani and O. Peleg, “On diagnosability of large fault sets in regular topology-based computer systems,” IEEE Transactions on Computers, 45(8): 892‒903, 1996.

[24] D. Wang, “Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model,” IEEE Transactions on Computers, 48(12): 1369‒1374, 1999.

[25] C.L. Yang, G.M. Masson, and R.A. Leonetti, “On fault isolation and identification in t₁ / t₁-diagnosable systems,” IEEE Transactions on Computers, 35(7): 639‒643, 1986.

[26] F. Barsi, F. Grandoni, and P. Maestrini, “A theory of diagnosability of digital systems,” IEEE Transactions on Computers, C-25(6): 585‒593, 1976.

[27] L.C. Albini, S. Chessa, and P. Maestrini, “Diagnosis of symmetric graphs under the BGM model,” The Computer Journal, 47(1): 85‒92, 2004.

[28] D.B. West, Introduction to Graph Theory, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2001.

[29] A.T. Dahbura and G.M. Masson, “An O (n^2.5) fault identification algorithm for diagnosable systems,” IEEE Transactions on Computers, 33(6): 486‒492, 1984.

[30] Y. Saad and M.H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, 37(7): 867‒872, 1988.

[31] K. Efe, “The crossed cube architecture for parallel computation,”IEEE Transactions on Parallel and Distributed Systems, 3(5): 513‒524, 1992.

[32] P. Kulasinghe, “Connectivity of the crossed cube,” Information Processing Letters, 61(4): 221‒226, 1997.

[33] P. Cull and S.M. Larson, “The M ö bius cubes,” IEEE Transactions on Computers, 44(5): 647‒659, 1995.

[34] P.A.J. Hilbers, M.R.J. Koopman, and J.L.A. van de Snepscheut, “The twisted cube,” in Proceedings of the Conference on Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, pp. 152‒159, 1987.

[35] C. Chang, J.N. Wang, and L.H. Hsu, “Topological properties of twisted cube,” Information Science, 113: 147‒167, 1999.

[36] X. Yang, D.J. Evans, and G.M. Megson, “The locally twisted cubes,”International Journal of Computer Mathematics, 82(4) 401‒413, 2005.

[37] F.B. Chedid, “On the generalized twisted cube,” Information Processing Letters, 55(1): 49‒52, 1995.

[38] F.B. Chedid and R.B. Chedid, “A new variation on hypercubes with smaller diameter,” Information Processing Letters, 46(6): 275‒280, 1993.

[39] J.H. Park, “Panconnectivity and edge-pancyclicity of faulty recursive circulant G (2 ^m, 4),” Theoretical Computer Science, 390(1): 70‒80, 2008.

[40] J.H. Park and K.Y. Chwa, “Recursive circulants and their embeddings among hyper-cubes,” Theoretical Computer Science, 244: 35‒62, 2000.

[41] F.T. Boesch and R. Tindell, “Circulants and their connectivities,” Journal of Graph Theory, 8: 129‒138, 1984.

[42] S.W. Jung, S.Y. Kim, J.H. Park, and K.Y. Chwa, “Connectivities of recursive circulant graphs,” in Proceedings of the 19th KISS Spring Conference, pp. 591‒594, 1992.

[43] S.K. Das and A.K. Banerjee, “Hyper Petersen network: Yet another hypercube-like topology,” in Proceedings of the 4th Symposium on the Frontiers of Massively Parallel Computation (Froniters '92), McLean, VA, pp. 270‒277, IEEE Computer Society, 1992.

[44] S.K. Das, S.Ö hring, and A.K. Banerjee, “Embeddings into hyper Petersen networks: Yet another hypercube-like interconnection topology,” VLSI Design, 2(4): 335‒351, 1995.

[45] A.E.I. Awawy and S. Latifi, “Properties and performance of folded hypercubes,” IEEE Transactions on Parallel and Distributed Systems, 2(1): 31‒42, 1991.

[46] S.A. Choudum and V. Sunitha, “Augmented cubes,” Networks, 40(2): 71‒84, 2002.

 

¹The notation G–S represents the graph obtained by deleting all the nodes in S from G.