The g-Good-Neighbor Conditional Diagnosability of Exchanged Crossed Cube under the MM* Model

Abstract

Diagnosability plays an important role in appraising the reliability and fault tolerance of symmetrical multiprocessor systems. The novel g-good-neighbor conditional diagnosability restrains that every fault-free node contains at least g fault-free neighbors and is suitable for large scale multiprocessor systems, attracting a lot of research attention. The relationships between the g-good-neighbor connectivity and g-good-neighbor diagnosability of graphs under the $M{M}^{*}$ model are separately studied, but only applicable in regular graphs or just ranges rather than exact values. As a promising network structure, in 2019, Guo et al. obtained that the g-good-neighbor diagnosability of the exchanged crossed cube ($ECQ\left(s,t\right)$) under the PMC model is $2^g\left(s+2-g\right)-1$ ($t\ge \mathrm{s}>g$). We noticed that the exact value of the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$ under the $M{M}^{*}$ model is still to be determined. In this paper, by proving the upper and lower bounds of the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$, for the first time, we derive that the exact value of its g-good-neighbor diagnosability under the $M{M}^{*}$ model is $t_g^m\left(ECQ\left(s,t\right)\right)=2^g\left(s+2-g\right)-1$ ($t\ge \mathrm{s}>g$), achieving the unity of the g-good-neighbor diagnosability of ECQ(s, t) under both the PMC model and $M{M}^{*}$ model. Towards the end, simulation experiments are conducted to evaluate the correctness and effectiveness of our conclusion. Our research provides an important supplement to the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$.

1. Introduction

In a high performance computing (HPC) system, millions of processors are interconnected to implement large scale parallel computation, and the interconnection network is always abstracted as an undirected connected graph G(V, E), where V and E represent the node set and link set, respectively. For example, according to the latest TOP 500 list in June 2022, Frontier and Supercomputer Fugaku, the two fastest supercomputers in the world, contain 8,730,112 and 7,630,848 processing nodes, respectively [1]. In such systems, it is inevitable that some processors may break down, and these faults must be treated uninterruptedly without shutting down the whole system. Therefore, the ability of identifying faulty nodes (or edges) is critical in enhancing fault tolerance and the reliability of interconnection networks, which is also called system fault diagnosability. A system G is called t-diagnosable if all the faulty nodes can be detected with the precondition that the faulty processor number is no more than t, and the maximum value of t is called the diagnosability of system G.

There are primarily two kinds of diagnosis models for determining multiprocessor system diagnosability according to different diagnostic strategies. In 1967, Preparata et al. [2] put forward the PMC model, and all tests are conducted between any two adjacent processors by testing each other. In 1980, Malek et al. [3] proposed the comparison diagnosis model, and Maeng and Malek [4] extended this comparison model by allowing conducting comparisons by the processors themselves, i.e., the MM model. Based on the MM model, Sengupta [5] further restricted that each processor must test its any two adjacent neighbors and proposed the MM* model, a special case of the MM model. The MM* model has been widely studied in the literature [6,7,8,9,10,11,12,13,14,15,16].

Connectivity determines the tolerance of the number of faulty nodes that could disrupt the whole interconnection network. However, it is unpractical in network fault diagnosis, because it is almost impossible that all the neighbor nodes of a processor break down simultaneously. In 2005, motivated by the conditional connectivity restricting that every node has at least one fault-free neighbor, Lai et al. [17] put forward the conditional diagnosability on the condition that all the neighbors of any node v cannot fail at the same time. It has been confirmed that the conditional diagnosability is much higher than traditional diagnosability and this has drawn a lot of research attention on many networks, such as the hypercubes [18], the exchanged hypercube [12], the (n, k)-star networks [19], the exchanged crossed cube [20], the folded hypercubes [21], the matching composition networks [22], and the Cayley graphs [23]. To further improve the system fault diagnosis capability of high-dimensional interconnection networks, Peng et al. [24] extended the conditional diagnosability to the g-good-neighbor conditional diagnosability (also called the g-good-neighbor diagnosability), requiring that every faulty-free node has at least g fault-free neighbors. Owing to its excellent fault diagnosis performance, the g-good-neighbor conditional diagnosability has also attracted much attention. Wang et al. [14,24] studied the g-good-neighbor diagnosability of the hypercube under the PMC and MM* model, respectively. Yuan et al. [25] studied the g-good-neighbor diagnosability of the k-ary n-cube (k$\ge 3$) under the PMC and MM* model. Ren and Wei et al. [26,27] independently researched the g-good-neighbor diagnosability of the locally twisted cube under the PMC and MM* model. The g-good-neighbor diagnosability of some network groups have also been studied, including the regular graphs [28,29] and the alternating group graphs [9,30].

To make the identification of the g-good-neighbor diagnosability more general, some researchers tried to reveal the relationship between the R_g-restricted connectivity and g-good-neighbor diagnosability. Lin et al. [31] proved that, for an r_d-regular network, the g-good-neighbor diagnosability under the PMC model is $t_g^p\left(G\right)=k^g\left(G\right)+\left|V\left(\widehat{L}\right)\right|-1$, and for an r_d-regular triangle-free network, the g-good-neighbor diagnosability under the MM* model is also $t_g^m\left(G\right)=k^g\left(G\right)+\left|V\left(\widehat{L}\right)\right|-1$, where $k^g\left(G\right)$ denotes the R_g-restricted connectivity. Cheng et al. [32] obtained that, for any k-regular graph with $2\le g<k$, the g-good-neighbor diagnosability under both the PMC and $M{M}^{*}$ model is $t_g\left(G\right)=k^{\left(g\right)}\left(G\right)+s-1$. Cheng et al. [33] further extended the conclusion to any connected graph that the g-good-neighbor diagnosability under the PMC satisfies $t_g\left(G, PMC\right)\ge k_g\left(G\right)+g$ with $g\ge 1$, and similarly, under the MM* model there is $t_g\left(G, M{M}^{*}\right)\ge k_g\left(G\right)+g$ with $g\ge 2$. Wang et al. [34] independently proved that, for a g-good-neighbor connected graph, the g-good-neighbor diagnosability under the PMC satisfies $k^{\left(g\right)}\left(G\right)+\left|V\left(H^{\prime }\right)\right|-1\le t_g\left(G\right)\le k^{\left(g\right)}\left(G\right)+\left|V\left(H\right)\right|-1$, and under the MM* model there is $k^{\left(g\right)}\left(G\right)+\left|V\left(H^{\prime }\right)\right|-2\le t_g\left(G\right)\le k^{\left(g\right)}\left(G\right)+\left|V\left(H\right)\right|-1$.

As an important variant of the hypercube, the exchanged crossed cube [35] ($ECQ\left(s,t\right)$) inherits most of the appealing features of both the exchanged hypercube [36] ($EH\left(s,t\right)$) and crossed cube [37] ($C{Q}_n$), possessing smaller network diameter, lower hardware cost, and higher cost performance. Some of its characteristics on reliability and fault tolerance are explored, including its connectivity features [38,39,40], and the conditional diagnosability under both the PMC model and MM model [20,41]. In 2019, Guo et al. [42] proved that the R_g-restricted connectivity of $ECQ\left(s,t\right)$ is $2^g\left(s+1-g\right)$ and the g-good-neighbor diagnosability under the PMC model is $2^g\left(s+2-g\right)-1$ ($t\ge \mathrm{s}>g$). However, after extensive analysis, we find that the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$ under the $M{M}^{*}$ model is still undetermined. Theoretically, based on the proven R_g-restricted connectivity of $ECQ\left(s,t\right)$ and the relationship between the R_g-restricted connectivity and g-good-neighbor diagnosability, it is easy to calculate the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$ under the $M{M}^{*}$ model. However, the conclusions in the literature [31,32] are only applicable to regular graphs, whereas $ECQ\left(s,t\right)$ is obviously not a regular graph when $s\ne t$; the conclusions in the literature [33,34] are just two range inequalities, and it is quite difficult to infer the exact value of the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$. Therefore, we must find another way to obtain the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$.

In this paper, by proving the upper and lower bounds of the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$, we obtain the exact value of the $g$-good-neighbor diagnosability of $ECQ\left(s,t\right)$ under the $M{M}^{*}$ model and carry out simulation experiments to evaluate the correctness and effectiveness of our conclusion.

The rest of this paper is organized as follows. Some terminologies and preliminaries are introduced in Section 2. The $g$-good-neighbor conditional diagnosability of $ECQ\left(s,t\right)$ under the $M{M}^{*}$ model is proved in Section 3. Simulation experiments are conducted in Section 4. We then conclude this paper in Section 5.

2. Preliminaries

2.1. Notations

In a multiprocessor system, the interconnection network is always abstracted as a graph $G\left(V,E\right)$, where V represents the node set and E the edge set, i.e., $\forall u, v\in V$, $\left(u,v\right)\in E$. u[i] denotes the i-th bit of node u, and u[i:j] denotes a binary string starting from the i-th bit to the j-th bit. N(u) denotes the neighbor node set in which all nodes are directly connected to u. For $\forall u\in V$, $d\left(u\right)$ represents the degree of node $u$. Let $F\subseteq V$, and the subgraph $G-F$ is constructed by deleting all nodes and all related edges in $F$ from graph $G$. If $G-F$ is not connected, $F$ is called the cut of $G$, and the minimum cardinality of cuts is called the connectivity of G, denoted by $k\left(G\right)$ (or $\lambda \left(G\right)$). For any two sets $F_1$ and $F_2$, their symmetric difference is defined as $F_1\Delta F_2=(F_1-F_2){{\displaystyle \cup }}^{ }\left(F_2-F_1\right)$. For other terminologies and notations not mentioned in this paper, readers may also refer to [43].

2.2. The MM* Model

In the MM model [4], a comparator node sends a testing task to any two pairs of its neighbors and compares the results. The MM model always follows the following assumptions: (1) all faults are everlasting; (2) the outputs of a faulty processor for its each given task are incorrect; and (3) the comparison result performed by a faulty processor is unreliable. For any three processors $\forall u, v, w\in V$ in a system G, if w is a fault-free processor and is applied as a tester on u and v, the output result can be denoted with $\sigma \left({\left(u,v\right)}_w\right)$, where $\left(u, w\right), \left(v, w\right)\in E\left(G\right)$ represents a test conducted by w, and $\left(u, w\right), \left(v, w\right)\in E\left(G\right)$. If the test ${\left(u,v\right)}_w$ contradicts, $\sigma \left({\left(u,v\right)}_w\right)=1$; otherwise, $\sigma \left({\left(u,v\right)}_w\right)=0$. The collection of all test results is called a syndrome of the diagnosis on G, denoted by $\sigma \left(G\right)$. The $M{M}^{*}$ model [5] developed the MM model such that the comparisons need no central unit and any processor node itself can be used as a comparator, which is a special case of the MM model.

2.3. Connectivity and Diagnosability

A fault set $F\subseteq V$ is called a $g$-good-neighbor conditional fault set [24] if $\left|N\left(v\right){{\displaystyle \cap }}^{ }\left(G-F\right)\right|\ge g$, $\forall v\in G-F$. A $g$-good-neighbor conditional cut of $G$ is a $g$-good-neighbor conditional fault set $F$ such that $G-F$ is disconnected. The $g$-good-neighbor connectivity [44] (namely the R_g-restricted connectivity) of $G$, denoted with $k^{\left(g\right)}\left(G\right)$, is the minimum cardinality of $g$-good-neighbor faulty cuts.

Two distinct faulty sets $F_1,F_2\subset V\left(G\right)$ are distinguishable if $\sigma \left(F_1\right){{\displaystyle \cap }}^{ }\sigma \left(F_2\right)=\varnothing$; otherwise, $F_1$ and $F_2$ are indistinguishable. A system $G$ is t-diagnosable if any two distinct faulty sets $F_1,F_2\subset V\left(G\right)$ are distinguishable, where $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$. Sengupta et al. [5] propose a sufficient and necessary condition for judging whether two distinct sets $F_1$ and $F_2$ are distinguishable under the $M{M}^{*}$ model.

Theorem 1 

[5]. For any two distinct subsets $F_1$ and $F_2$ of $V\left(G\right)$, ($F_1$, $F_2$) is a distinguishable pair under the $M{M}^{*}$ mode if and only if one of the following conditions is satisfied (see Figure 1):

• There are two vertices $u, w\in V\left(G\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)$ and there is a vertex $v\in F_1\Delta F_2$such that $\left(u, w\right)\in E\left(G\right)$ and $\left(v, w\right)\in E\left(G\right)$;
• There are two vertices $u, v\in F_1-F_2$ and there is a vertex $w\in V\left(G\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)$ such that $\left(u, w\right)\in E\left(G\right)$ and $\left(v, w\right)\in E\left(G\right)$;
• There are two vertices $u, v\in F_2-F_1$ and there is a vertex $w\in V\left(G\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)$ such that $\left(u, w\right)\in E\left(G\right)$ and $\left(v, w\right)\in E\left(G\right)$;

Figure 1. The illustrations of conditions in Theorem 1 under the $M{M}^{*}$ model. (a) Condition (1) of a distinguishable pair; (b) Condition (2) of a distinguishable pair; (c) Condition (3) of a distinguishable pair.

Figure 1. The illustrations of conditions in Theorem 1 under the $M{M}^{*}$ model. (a) Condition (1) of a distinguishable pair; (b) Condition (2) of a distinguishable pair; (c) Condition (3) of a distinguishable pair.

In this paper, we use the extended definition of the conditional diagnosability proposed by Peng et al. [24], as is defined in Definition 1.

Definition 1 

[24]. A system $G=\left(V,E\right)$ is $g$-good-neighbor conditionally $t$-diagnosable if each distinct pair of $g$-good-neighbor conditional fault sets $F_1\subseteq V$ and $F_2\subseteq V$ (with $\left|F_1\right|\le t$, $\left|F_2\right|\le t$) are distinguishable. The $g$-good-neighbor conditional diagnosability of G is the maximum t such that G is $g$-good-neighbor conditional $t$-diagnosable, denoted with $t_g\left(G\right)$.

2.4. The Exchanged Crossed Cube

The exchanged crossed cube [35] ($ECQ\left(s,t\right)$) combines the advantages of the exchanged cube [36] and the crossed cube [37] and retains many desirable characteristics, such as good cost-effectiveness, high partitionability, and strong fault tolerance.

Definition 2. 

Two binary strings$x=x_1{x}_2$and$y=y_1{y}_2$are pair related if and only if$\left(x, y\right)\in${(00,00), (10, 10), (01, 11), (11, 01)}, denoted by$x~y$.

An exchanged crossed cube $ECQ\left(s,t\right)$ can be modeled as an undirected graph G(V, E), where V = {a_s−1 a_s−2…a₀ b_t−1 b_t−2…b₀c│a_i, b_j, c ∈ {0,1}, i ∈[0,s], j ∈ [0,t]}, $E=\left\{\left(u,v\right)|\left(u,v\right)\in V\times V\right\}$, which consists of three types of edges, namely $E_1$, $E_2$, and $E_3$, defined as follows [42]:

• $\left(u,v\right)\in E_1$: implies that $u\left[0\right]\ne v\left[0\right]$, $u\left[s+t:1\right]=v\left[s+t:1\right]$;
• $\left(u,v\right)\in E_2$: implies that $u\left[0\right]=v\left[0\right]=0$, $u\left[t:1\right]=v\left[t:1\right]$, there exists an integer $l$ ($s+t\le l\le t+1$) such that $u\left[s+t:l\right]=v\left[s+t:l\right]$, $u\left[l-1\right]\ne v\left[l-1\right]$; if $l-t$ is even, $u\left[l-2\right]=v\left[l-2\right]$, $u\left[t+2i+2:t+2i+1\right] ~ v\left[t+2i+2:t+2i+1\right]$, where $\left(l-t-1\right)/2>i\ge 0$;
• $\left(u,v\right)\in E_3$: implies that $u\left[0\right]=v\left[0\right]=1$, $u\left[s+t:t+1\right]=v\left[s+t:t+1\right]$, there exists an integer $l$ ($1\le l\le t$) such that $u\left[t:l\right]=v\left[t:l\right]$, $u\left[l-1\right]\ne v\left[l-1\right]$; if $l-t$ is even, $u\left[l-2\right]=v\left[l-2\right]$, $u\left[2i+2:2i+1\right] ~ v\left[2i+2:2i+1\right]$, where $\left(l-1\right)/2>i\ge 0$.

The following Figure 2 shows an example of $ECQ\left(1,2\right)$.

Theorem 2

[42]. The $R_g$-connectivity of $ECQ\left(s,t\right)$ is $k^{\left(g\right)}\left(ECQ\left(s,t\right)\right)=2^g\left(s+1-g\right)$, where $t\ge s\ge g\ge 0$.

Lemma 1 

[42]. Among all nodes of $ECQ\left(s,t\right)$, the degree of the node with c = 0 is $s+1$, and the degree of the node with c = 1 is $t+1$.

3. The g-Good-Neighbor Conditional Diagnosability of ECQ(s,t) under the MM* Model

In this section, we will prove the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$ by getting its upper and lower bounds separately, and the symbol $t_g^m\left(G\right)$ is applied to represent the $g$-good-neighbor conditional diagnosability of G under the $M{M}^{*}$ model.

Theorem 3.

$t_g^m\left(ECQ\left(s,t\right)\right)\le 2^g\left(s+2-g\right)-1$, ($2\le s\le t$, $0\le g\le s$).

Proof of Theorem 3.

Let $A=\left\{{\ast }^g{0}^{\left(s+t+1-g\right)}|\ast \in \left\{0,1\right\}\right\}$, $A\subseteq ECQ\left(s,t\right)$, the rightmost ($s+t+1-g$) bits of $A$ are all 0′s. Let the fault set $F_1=N\left(A\right)=\left\{{\ast }^g{0}^p{10}^{s-g-p-1}{0}^{t+1}\right\}{\displaystyle \cup }\left\{{\ast }^g{0}^{s+t-g}1\right\}$, where $s-g-1\ge p\ge 0$, $\ast \in \{0,1\}$; let the fault set $F_2=N\left(A\right){\displaystyle \cup }A=\left\{{\ast }^g{0}^p{10}^{s-g-p-1}{0}^{t+1}\right\}{\displaystyle \cup }\left\{{\ast }^g{0}^{s+t-g}1\right\}{\displaystyle \cup }\left\{{\ast }^g{0}^{s+t+1-g}\right\}$, where $s-g-1\ge p\ge 0$, $\ast \in \{0,1\}$. Obviously, we have $\left|F_1\right|=2^g\left(s+1-g\right)$, $\left|F_2\right|=2^g\left(s+2-g\right)$ and $F_1\subset F_2$.

Let $B=V\left(ECQ\left(s,t\right)\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)$ (see Figure 3). Assume that $B$ consists of three subsets, i.e., $B=B_1{{\displaystyle \cup }}^{ }{B}_2{{\displaystyle \cup }}^{ }{B}_3$, as are defined as follows:

$$B_1=\left\{{\ast }^g{a}_{s+t-g}\dots a_2{a}_{1}1\right\}, \mathrm{there} \mathrm{is} \mathrm{at} \mathrm{least} \mathrm{one} ‘1’ \mathrm{bit} \mathrm{in} a_{s+t-g}\dots a_2{a}_1.$$

$$B_2=\left\{{\ast }^g{a}_{s-g}\dots a_2{a}_1{\ast }^{t}0\right\}, \mathrm{there} \mathrm{are} \mathrm{at} \mathrm{least} \mathrm{two} ‘1’ \mathrm{bits} \mathrm{in} a_{s-g}\dots a_2{a}_1.$$

$$B_3=\left\{{\ast }^g{a}_{s+t-g}\dots a_2{a}_{1}0\right\}, \mathrm{there} \mathrm{is} \mathrm{at} \mathrm{least} \mathrm{one} ‘1’ \mathrm{bit} \mathrm{in} a_{s+t-g}\dots a_2{a}_1.$$

Then, we will discuss whether every node $u\in B$ has g neighbors or not according to the following three cases.

• Case 1: $\forall u\in B_1$

According to the definitions of $B_1$ and $F_1{{\displaystyle \cup }}^{ }{F}_2$, only when $u\in \left\{{\ast }^g{0}^{s+t-g-1}11\right\}\subset B_1$, there exists one edge between $B_1$ and $F_1{{\displaystyle \cup }}^{ }{F}_2$, i.e., node $u$ has at most 1 neighbor belonging to $F_1{{\displaystyle \cup }}^{ }{F}_2$. By Lemma 1, $\delta \left(u\right)=s+1$. Except for the neighbors belonging to $F_1{{\displaystyle \cup }}^{ }{F}_2$, all the other $s$ ($s>g$) neighbors of $u$ belong to $\forall u\in B_2$.

• Case 2: $\forall u\in B_2$

By the definition of $B_2$, only when $u\in \left\{{\ast }^g{0}^q{110}^{s-g-q-2}{0}^{t+1}\right\}\subset B_2$ $,\mathrm{where} s-g-1\ge q\ge 0$, $u$ has at most 1 neighbors belonging to $F_1{{\displaystyle \cup }}^{ }{F}_2$. By Lemma 1, $\delta \left(u\right)=s+1$. There are $s$ ($s>g$) neighbors of $u$ belonging to $B$.

• Case 3: $\forall u\in B_3$

All $s+1>g$ neighbors of node $u$ belong to $B$ by the definition of $B_3$, and no neighbor belongs to $F_1{{\displaystyle \cup }}^{ }{F}_2$.

In summary, we can see that every node of $B$ has $g$ neighbors in $B$.

According to the above assumption, we have $F_1\Delta F_2=N\left(A\right)\Delta \left(N\left(A\right){{\displaystyle \cup }}^{ }A\right)=A$, and $V\left(ECQ\left(s,t\right)\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)=V\left(ECQ\left(s,t\right)\right)-\left(N\left(A\right){{\displaystyle \cup }}^{ }\left(N\left(A\right){{\displaystyle \cup }}^{ }A\right)\right)$. It can be inferred that any node $u\in N\left(A\right)$ must not exist in $V\left(ECQ\left(s,t\right)\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)$, i.e., there is no edge between $V\left(ECQ\left(s,t\right)\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)$ and $F_1\Delta F_2$. By Theorem 1, $\left(F_1,F_2\right)$ is an indistinguishable pair under the $M{M}^{*}$ model.

By Definition 1, $ECQ\left(s,t\right)$ is not $g$-good-neighbor conditional $2^g\left(s+2-g\right)$-diagnosable under the $M{M}^{*}$ model. $\left|F_2\right|=2^g\left(s+2-g\right),$ $t_g^m\left(ECQ\left(s,t\right)\right)<\left|F_2\right|$. Thus, the upper bound of the $g$-good-neighbor conditional diagnosability of $ECQ\left(s,t\right)$ is $t_g^m\left(ECQ\left(s,t\right)\right)\le 2^g\left(s+2-g\right)-1$ for $2\le s\le t$, $0\le g\le s$. □

Theorem 4.

$t_g^m\left(ECQ\left(s,t\right)\right)\ge 2^g\left(s+2-g\right)-1$, ($2\le s\le t$, $0\le g\le s$).

Proof of Theorem 4.

Assume that each distinct $g$-good-neighbor conditional fault sets $F_1$ and $F_2$ of $ECQ\left(s,t\right)$ are indistinguishable. By Theorem 3, $\left|F_1\right|,\left|F_2\right|\le 2^g\left(s+2-g\right)-1$. We will first prove that $V\left(ECQ\left(s,t\right)\right)\ne F_1{{\displaystyle \cup }}^{ }{F}_2$.

Now we suppose $V\left(ECQ\left(s,t\right)\right)=F_1{{\displaystyle \cup }}^{ }{F}_2$, then there is $\left|F_1{{\displaystyle \cup }}^{ }{F}_2\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|\le \left|F_1\right|+\left|F_2\right|\le 2\left(2^g\left(s+2-g\right)-1\right)$. Since $V\left(ECQ\left(s,t\right)\right){=2}^{s+t+1}$, we have $\left|V\left(ECQ\left(s,t\right)\right)\right|-\left|F_1{{\displaystyle \cup }}^{ }{F}_2\right|\ge 2^{s+t+1}-2\left(2^g\left(s+2-g\right)-1\right)$. Let $h\left(g\right)=2^{s+t+1}-2\left(2^g\left(s+2-g\right)-1\right)$, there is $\frac{\partial \left(h\left(g\right)\right)}{\partial g}=2^{\mathrm{g}+1}\left[g\ln 2+1-\ln 2\left(s+2\right)\right]<0$, indicating that $h\left(g\right)$ is a decreasing function. Then $h\left(g\right)\ge h\left(s\right)=2^{s+t+1}-2^{s+2}+2>0$, i.e., $\left|V\left(ECQ\left(s,t\right)\right)\right|-\left|F_1{{\displaystyle \cup }}^{ }{F}_2\right|\ge h\left(g\right)>0$, a contradiction with the hypothesis that $V\left(ECQ\left(s,t\right)\right)=F_1{{\displaystyle \cup }}^{ }{F}_2$. Therefore, we can obtain that $V\left(ECQ\left(s,t\right)\right)\ne F_1{{\displaystyle \cup }}^{ }{F}_2$.

Without loss of generality, we assume that $F_1-F_2\ne \varnothing$ in the following derivation. Let $W$ be the set of isolated vertices in $\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2$. $W\subseteq V\left(ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2\right)$, see Figure 4.

Let $H=\left[V\left(ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2\right)-W\right].$ We will show that $W=\varnothing ,$ by considering the following three cases.

• Case 1. $g=1$.

Suppose $W\ne \varnothing$, $w\in W$. Since $F_1$ is a 1-good-neighbor conditional fault-set, $w$ must be adjacent to at least one node $u$ of $F_2-F_1$. By Theorem 1(3), we can deduce that $\exists v\in F_1-F_2$, such that $v$ is adjacent to $w$, $\left|N\left(w\right){{\displaystyle \cap }}^{ }{F}_i\right|=1$, for $i=1,2$. Moreover, for any node $w\in W$, node $w$ has $s+1-2$ neighbors in $F_1{{\displaystyle \cap }}^{ }{F}_2$. Since $\left|F_2\right|\le 2^g\left(s+2-g\right)-1$ and $g$ = 1, there is $\left|F_2\right|\le 2\left(s+1\right)-1$. Let $N_{F_1{{\displaystyle \cap }}^{ }{F}_2}\left(w\right)$ be the neighbors of node $w$ belonging to $F_1{{\displaystyle \cap }}^{ }{F}_2.$ Therefore, we have

$$\begin{array}{c}{\displaystyle {\displaystyle \sum }_{w\in W}}\left|N_{F_1{{\displaystyle \cap }}^{ }{F}_2}\left(w\right)\right|=\left|W\right|\left[\left(s+1\right)-2\right]\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} \hspace{1em}\hspace{1em}\le {\displaystyle \sum }_{v\in F_1{{\displaystyle \cap }}^{ }{F}_2}d\left(v\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} \hspace{1em} \le \left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|\left(s+1\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em} \hspace{1em}\hspace{1em}\hspace{1em}\le \left(2\left(s+1\right)-1-1\right)\left(s+1\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} =2s\left(s+1\right)\hfill \end{array}$$

So $\left|W\right|\le \frac{2s\left(s+1\right)}{\left(s+1\right)-2}=\frac{2s\left(s+1\right)}{s-1}$,

Assume $H=\varnothing$ and substitute $\left|W\right|$ into the following formula, we obtain

$$\begin{array}{c}{2}^{s+t+1}=\mid V\left(ECQ\left(s,t\right)\right|\hfill \\ \hspace{1em}=\left|F_1{{\displaystyle \cup }}^{ }{F}_2\right|+\left|W\right|\hfill \\ \hspace{1em}\le \left|F_1\right|+\left|F_2\right|-\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|+\left|W\right|\hfill \\ \hspace{1em}\le 2\left[2\left(s+1\right)-1\right]-\left[\left(s+1\right)-2\right]\hfill \\ \hspace{1em}\hspace{1em}+\frac{2s\left(s+1\right)}{s-1}\hfill \\ \hspace{1em}=\frac{\left[\left(5s-3\right)\left(s+1\right)\right]}{s-1}\hfill \end{array}$$

However, for $2\le s\le t$, $0\le g\le s$, there is $2^{s+t+1}\ge 2^{s+3}>\frac{\left[\left(5s-3\right)\left(s+1\right)\right]}{s-1}$, which obviously contradicts the above inequality. Therefore, H ≠ Ø.

Since the fault pair $\left(F_1,F_2\right)$ are indistinguishable by the condition (1) of Theorem 1, $F_1{{\displaystyle \cap }}^{ }{F}_2$ is a $R_1$-cut of $ECQ\left(s,t\right)$. By Theorem 2, $\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|\ge 2\left(s+1\right)-1$. Note that for any node $w$, $\left|N\left(w\right){{\displaystyle \cap }}^{ }{F}_i\right|=1$ ($i=1,2$), we have $\left|F_1\right|\le 2\left(s+1\right)$, $\left|F_2\right|\le 2\left(s+1\right)$ and $F_1-F_2\ne \varnothing ,$ $F_2-F_1\ne \varnothing$. Thus, $\left|F_2-F_1\right|=\left|F_1-F_2\right|=1$.

Let $F_1-F_2=\left\{v_1\right\}$ and $F_2-F_1=\left\{v_2\right\}$. Hence, any $w\in W$ is adjacent to $v_1$ and $v_2$, $v_1,v_2\in N\left(w\right)$.

• Subcase 1.1. $\left|W\right|=1$.

Let $\forall w\in W$, we have

$$\begin{gathered} N_1=N_{ECQ\left(s,t\right)}\left(w\right)-\left\{v_1,v_2\right\}\subset F_1{{\displaystyle \cap }}^{ }{F}_2 \\ {N}_2=N_{ECQ\left(s,t\right)}\left(v_1\right)-\left\{w\right\}\subset F_1{{\displaystyle \cap }}^{ }{F}_2 \\ {N}_3=N_{ECQ\left(s,t\right)}\left(v_2\right)-\left\{w\right\}\subset F_1{{\displaystyle \cap }}^{ }{F}_2 \\ N_i{{\displaystyle \cap }}^{ }{N}_j=\varnothing ,i,j\in \left\{1,2,3|i\ne j\right\} \end{gathered}$$

Thus, $2\left(s+1\right)-1=\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|>\left|N_1\right|+\left|N_2\right|+\left|N_3\right|=s-1+s+s=3s-1,$ we have $s<2$, which contradicts with $s\ge 2$, therefore, $\left|W\right|\ne 1$.

• Subcase 1.2. $\left|W\right|\ge 2$.

According to the basic properties of $ECQ\left(s,t\right)$, any pair of distinct vertices in $ECQ\left(s,t\right)$ has at most two common neighbors. Since $\left|W\right|\ge 2,$ there are at most two common neighbors $w_1,w_2$ $\in$ $W$. In addition, $ECQ\left(s,t\right)$ is a $1$-good-neighbor conditional diagnosable system, so there is an edge between $w_1$ and $w_2$, which contradicts with the assumption that $W$ is a set of isolated nodes.

• Case 2. $g\ge 2$.

Since $F_1$ is a $g$-good-neighbor conditional fault-set, for every $x\in V\left(ECQ\left(s,t\right)\right)-F_1$, we have $\left|N_{ECQ\left(s,t\right)-F_1}\left(x\right)\right|\ge g$. Because $\left(F_1,F_2\right)$ is a indistinguishable pair, by Theorem 1(3), any node $w$ in $V\left(ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2\right)$ has at most one neighbor in $F_2-F_1$, thus $\left|N_{ECQ\left(s,t\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)}\left(w\right)\right|\ge g-1\ge 1$, and every node of $ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2$ is not isolated.

Let $u\in ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2$, since every node of $ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2$ is not isolated, $u$ has at least one neighbor $v$ in $ECQ\left(s,t\right)-F_1{{\displaystyle \cup }}^{ }{F}_2$. Because $\left(F_1,F_2\right)$ is an indistinguishable pair, there is no edge between $V\left(ECQ\left(s,t\right)-\left(F_1{{\displaystyle \cup }}^{ }{F}_2\right)\right)$ and $F_1\Delta F_2$. $F_1{{\displaystyle \cap }}^{ }{F}_2$ is also a $R_g$-cut of $V\left(ECQ\left(s,t\right)\right)$. By Theorem 2, $\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|\ge 2^g\left(s+1-g\right)$. Therefore,

$$\begin{array}{c}\left|F_2\right|=\left|F_2-F_1\right|+\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|\hfill \\ \hspace{1em} \ge 2^g+2^g\left(s+1-g\right)\hfill \\ \hspace{1em} =2^g\left(s+2-g\right)\hfill \end{array}$$

A contradiction with $\left|F_2\right|\le 2^g\left(s+2-g\right)-1$.

• Case 3. $g=0$.

There is a contradiction between $\left|F_2\right|=\left|F_2-F_1\right|+\left|F_1{{\displaystyle \cap }}^{ }{F}_2\right|\ge s+3$ and $\left|F_2\right|\le 2^g\left(s+2-g\right)-1=s+1$.

In summary, we can draw the conclusion that $t_g^m\left(ECQ\left(s,t\right)\right)\ge 2^g\left(s+2-g\right)-1$. Theorem 4 is proved. □

Combining Theorems 3 and 4, we have our main result as the following theorem 5.

Theorem 5.

$t_g^m\left(ECQ\left(s,t\right)\right)=2^g\left(s+2-g\right)-1,$ ($2\le s\le t$, $0\le g\le s$).

4. Simulation Experiment and Analysis

In this section, a simulation experiment and analysis on $g$-good-neighbor conditional diagnosability of $ECQ\left(s,t\right)$ ($2\le s\le t$, $0\le g\le s$) will be carried out. The development tools and experimental environment configurations are listed in

Table 1. Simulation experiment configurations and development tools.

Platform Attribute	Details
RAM	8.0 G
CPU	Intel(R) Core(TM) i7-9750H CPU @2.60 GHz 32-core processor
GPU	NVIDIA GeForce GTX 1650
Operating System	Windows 10
Development tools	Python-3.8, neo4j-community-4.3.3, JDK11
Runtime environment	python3, JDK 11 or above
Development languages	Python, Java, Cyper

.

The fault diagnosis simulation experiment mainly includes three parts: (1) construct the network structure; (2) generate random g-good-neighbor conditional fault sets $F_k$ (k = 1, 2 …); and (3) check the distinguishability of fault sets. We utilized the graph database Neo4j to construct a network model and set random fault nodes. The idea of judging distinguishability was inspired by the paper [42]. The experiment process is shown in Figure 5.

The detailed steps of the experiment are as follows.

• STEP 1: Construct the network structure.

The network model construction first encodes all nodes of $ECQ\left(s,t\right)$, and each node is represented by a binary string with $s+t+1$ bits. After that, according to the definition of $ECQ\left(s,t\right)$, the node adjacency conditions are divided into three different construction conditions, corresponding to $E_1, E_2$, and $E_3$ in the definition, and traverse all nodes for pairwise link matching. All adjacent nodes are stored in the form of connected edge 2-tuples to simulate a large-scale new interconnection network.

• STEP 2: Random generate g-good-neighbor conditional fault sets $F_k$ (k = 1, 2).

The idea of Algorithm 1 is to set the random faulty nodes and simulate the network fault state that satisfies the $g$ good neighbor condition failure. First, traverse all the nodes and calculate the number of adjacent nodes. Then, nodes that satisfy $\left|N\left(u\right)\right|\le \left|F\right|$ are randomly selected as faulty nodes, and these faulty nodes are randomly assigned into $F_1$ and $F_2$ fault sets. Finally, verify whether the number of neighbors of the correct node is greater than or equal to $g$. If yes, output the fault set $F_1$ and $F_2$; otherwise, repeat the process of randomly selecting the faulty nodes.

Algorithm 1: Generate g-good-neighbor fault sets

Input:g, |F|, nodes, tuples

Output:g-good-neighbor fault sets F1, F2

1 nodeMap = {};

2 F1 = {};

3 F2 = {};

4 for node ∈ nodes

5  nodeMap = Map(node, CountNeighbor (FindNeighber (node))

6 end for

7 for node ∈ nodes

8  (F1, F2) = SelectRandomNodes(nodes, |F|)

9    if node ∉ F1 OR node ∉ F2

10     if nodeMap(node) <g

11     then

12      continue

13     else

14      return (F1, F2)

15     end if

16    end if

17 end for

• STEP 3: check the distinguishability of fault sets.

Algorithm 2 is to check the distinguishability of fault sets under the MM* model. According to Theorem 1, it is judged whether the set of nodes meets the condition that the set of g-good-neighbor faults can be distinguished in pairs. The idea of this algorithm is to traverse all nodes in $F_1$ and $F_2$ to find and record their adjacent nodes. Then, calculate the repetition frequency of the same neighbors among all neighbors, and record the maximum repetition frequency. If the maximum repetition frequency is greater than or equal to 2, then $F_1$ and $F_2$ are distinguishable; otherwise, $F_1$ and $F_2$ are indistinguishable.

Algorithm 2: Distinguishable verification algorithm

Input:F1, F2

Output: Distinguishable verification result of F1 and F2

1 for node ∈ F1 ∈ F2

2    NeighborNode = FindNeighbor (node)

3    AllNeighborNode = addNeighborNode (NeighborNode)

4 end for

5 MaxFrequency = Max (CountFrequency (AllNeighborNode))

6 if MaxFrequency ≥ 2

7    return distinguishable = true

8 else

9    return distinguishable = false

10 end if

The number of faulty nodes is recorded as $\left|F\right|$, and the number of faulty nodes is increased by one every cycle from 1 until the fault set fails to satisfy the distinguishable condition. From the definition, it can be seen that the fault diagnosis degree of g-good neighbor is $\left|F\right|$ − 1.

Simulation experiments were performed, and the results were compared and analyzed in

Table 2. Simulation experiment results.

$s$	$\mathit{t}$	Node Number	Edge Number	$\mathit{g}$	|${\mathit{t}}_{\mathit{g}}^{\mathit{m}}$|
2	2	32	48	1	5
2	3	64	112	1	5
2	4	128	256	1	5
2	5	256	576	1	5
3	3	128	256	1	7
3	3	128	256	2	11
3	4	256	576	1	7
3	4	256	576	2	11
3	5	512	1280	1	7
3	5	512	1280	2	11
4	4	512	1280	1	9
4	4	512	1280	2	15
4	4	512	1280	3	23
4	5	1024	2816	1	9
4	5	1024	2816	2	15
4	5	1024	2816	3	23
5	5	2048	6144	1	11
5	5	2048	6144	2	19
5	5	2048	6144	3	31
5	5	2048	6144	4	47

. We can see that the simulation experiment results are consistent with the theoretical derivation, which further confirms the correctness of our proven g-good-neighbor conditional diagnosability of $ECQ\left(s,t\right)$ under the $M{M}^{*}$ model.

According to Theorem 5, let the g-good-neighbor diagnosability of the $ECQ\left(s,t\right)$ be a binary function, i.e., $z=f\left(x,y\right)=2^x\left(y+2-x\right)-1$ ($2\le x\le y$), with x and y respectively representing the value of $g$ and $s$ in Theorem 5. Its three-dimensional function image is shown in Figure 6, and can be observed that z increases with the growth of either x or y. It can be concluded that the g-good-neighbor diagnosability of the $ECQ\left(s,t\right)$ positively correlates with the value g or the network scale s. Therefore, the g-good-neighbor diagnosability is an effective and promising fault diagnosis strategy and is especially suitable for large scale network fault diagnosis.

5. Conclusions

The fault diagnosability of an interconnection network is critical for HPC systems. The exchanged crossed-cube network has drawn a lot of research attention owing to its preferable network performance and has been applied into the design of large-scale parallel computing systems. However, the study on its fault diagnosis ability is still not enough, especially given that the exact value of its $g$-good-neighbor fault diagnosability under the $M{M}^{*}$ model is still to be determined. Based on the topological properties and connectivity theorem, this paper proved that the $g$-good neighbor diagnosis of exchanged crossed cube under the $M{M}^{*}$ model is $t_g^m\left(ECQ\left(s,t\right)\right)=2^g\left(s+2-g\right)-1$. Simulation experiments were conducted to verify the correctness and effectiveness of our conclusion. The research results provide important contributions to the research of the g-good-neighbor diagnosability of $ECQ\left(s,t\right)$ and has important theoretical significance and application value on the research of high-performance interconnection networks.