Abstract With the growing scale and complexity of high-performance computing systems, ensuring reliability through robust fault diagnosis becomes increasingly critical. System-level diagnosis plays a key role in identifying faulty processors and maintaining system stability of multiprocessor systems. However, traditional diagnosability, as a global reliability metric for multiprocessor systems, overlooks local diagnostic capability, topological criticality, and fault distribution. In order to better capture the local characteristics of a system around a given node, this work proposes a novel fault diagnosis strategy, called cyclic local diagnosability, where the cyclic fault pattern requires that at least two components contain cycles. We propose some characterizations of cyclic local diagnosability of interconnection networks under PMC and MM* models. As applications, we determine the cyclic local diagnosabilities of data center network DCell ($D_{k,n}$), $(n,k)$-star graph ($S_{n,k}$) and $(n,k)$-bubble-sort graph ($B_{n,k}$) under PMC and MM* models. Finally, we show the superiority of the cyclic local diagnosability through comparison with other conditional diagnosabilities.

The rapid growth of cloud computing, big data processing, and high-performance applications has led to the urgent demand for fault-tolerant and scalable data center networks. In this paper, we propose a novel data center network, DCube, based on the$n$-dimensional dual-cube, which outperforms other newly proposed data center networks, such as HSDC, CSDC, and HHCube, in both bisection width and scalability. We first propose the shortest path algorithm within the logical graph${\mathcal {DC}}_{n}$of DCube and show its diameter and bisection width as$4n + 1$and$2^{2n-3}$, respectively. Next, we determine the$g$-good-neighbor connectivity and$g$-extra connectivity of${\mathcal {DC}}_{n}$, as well as the node and edge connectivity of${\mathcal {DC}}_{n}$. We then explore the$g$-good-neighbor diagnosability and$g$-extra diagnosability of${\mathcal {DC}}_{n}$based on the derived$g$-good-neighbor connectivity and$g$-extra connectivity. Finally, we propose a N-E-FD algorithm for fault identification with time complexity of$O(n^{2} 2^{2n-1})$, and validate its effectiveness and accuracy through simulations. The results demonstrate that DCube provides a robust, scalable, and efficient choice for the data center architectures.

As the scale of multiprocessor systems increases, so do the requirements for system reliability and security. Modeling how processors and links are connected in a multiprocessor system through a network topology (or graph) is an effective means to study the reliability of the system. Connectivity, one of the important concepts in graph theory, can be used as an indicator of multiprocessor system’s reliability. However, as classical connectivity is not well suited for practical applications, the concept of$g$-extra connectivity has been proposed to more accurately characterize system’s reliability. The exchanged crossed cube, an innovative network topology derived from the classical hypercube, achieves not only a smaller diameter (improving information transmission efficiency) but also fewer connecting edges (reducing hardware costs when scaling the network). In this article, we derive the$g$-extra connectivity of the exchanged crossed cube and comparatively analyze its advantages in reliability evaluation through simulations.

The rapid advancement of semiconductor technology has enabled the development of large-scale multiprocessor systems, which are crucial for high-performance computing systems, data centers, and cloud infrastructures. However, as these systems grow in complexity and scale, the assessment of reliability becomes an urgent issue that needs to be solved, which calls for effective fault diagnosis to detect failures and maintain system performance. To this end, the concept of$(t,k)$-diagnosis was introduced, which detects all failing nodes when their number is at most$k$, and otherwise identifies at least$k$failing nodes per iteration as long as the total number does not exceed$t$. While traditional fault diagnosis strategies are effective, they often encounter the restriction of objective circumstances. For instance, it is improbable that all nodes adjacent to a particular node fail simultaneously. To enhance the efficiency and accuracy of fault diagnosis, this work introduces the$g$-good-neighbor conditional$(t,k)$-diagnosis. It ensures each node owns no fewer than$g$neighbors that are fault-free to match actual environmental requirements. For a general multiprocessor system modeled by$G$, let$\kappa _{g}(G)$be the$g$-good-neighbor connectivity, and define$\delta$as the minimum degree and$\Delta$as the maximum degree of$G$. Under the PMC model, we not only propose two conditional$(t,k)$-diagnosis algorithms, but also prove that$G$is$g$-good-neighbor conditional$(\frac{g|V|-p}{\Delta +g-1}, \min \lbrace p, k_{g}(G)\rbrace)$-diagnosable when fathomed components arise, where$g\leq \lfloor \frac{\Delta +1}{2}\rfloor$and$p\geq 1$, while in the absence of fathomed components,$G$is$g$-good-neighbor conditional$(\frac{g|V| + |B| - 2}{\Delta +g-1}, \kappa _{g}(G))$-diagnosable, where$g\leq \min \lbrace \delta -2,\lfloor \frac{\Delta }{2}\rfloor \rbrace$,$\lambda = (g+1)|B|$,$|B| < \frac{2\lambda (|B| - 1)+(\delta \lambda - \hat{I}(\lambda))|V|}{(\Delta +\delta) \lambda - \hat{I}(\lambda)}$, and$\hat{I}(\lambda)$approximates the number of directed edges among$\lambda$nodes. Experimental results show that conditional$(t,k)$-diagnosis algorithms achieve perfect fault identification with low runtime and good scalability.

Fault diagnosis is constantly crucial to maintain a high level of multiprocessor systems’ reliability. In multiprocessor systems, global fault diagnosis has been extensively investigated under both deterministic and probabilistic models, while local fault diagnosis has only been committed to the deterministic models, such as PMC model and MM$^*$model. This work focuses on a probabilistic approach for local diagnosis at a node within the mixed structure under the PMC diagnostic model so that the state of this node can be identified correctly by utilizing maximum a posteriori probability. This work is devoted to the quantitative metric on global reliability of multiprocessor systems in terms of local fault probability of node under microscale. The proposed strategy effectively reduces diagnostic delays and enhances system response in practical applications and thus improves the efficiency and accuracy of fault detection. In addition, the probabilistic approach reduces the effect of uncertainty on the fault diagnosis, which in turn improves the reliability and safety of the system. In this work, we first perform a more precise syndrome analysis for this mixed structure under the PMC model by virtue of local testing results, and suggest a modified local diagnosis algorithm calledMLDA. Subsequently, we implement the maximum a posteriori probabilistic local diagnosis algorithm calledMAPPLDAfor the mixed structure under the probabilistic PMC diagnostic model. Finally, numerical simulation results confirm the effectiveness of the syndrome analysis approach and the maximum a posteriori probability approach for the mixed structure when the node failure probability is very small.

Reliability assessment of multiprocessor systems presents the theoretical foundation for the layout and optimization of multiprocessor systems. The$h$-extra edge-connectivity$\lambda _{h}$and the$k$-component edge-connectivity$c\lambda _{k}$, as extensions of the classical edge connectivity, are two precise metrics for the measurement of the reliability of multiprocessor systems. For multiprocessor systems, determining$c\lambda _{k}$and$\lambda _{k}$of a large$k$is still difficult. Let$\delta _{G}(0)=0$and$\delta _{G}(i)=\frac{1}{2}(\text{ex}_{i+1}(G)-\text{ex}_{i}(G))$for$i\in \lbrace 1, \ldots, |G|-1\rbrace$, where$\text{ex}_{i}(G)={\mathrm{max}}\lbrace 2|E(G[S])|: S\subseteq V(G), |S|=i \rbrace$. In this article, we obtain$c\lambda _{k}$and$\lambda _{h}$of the Cartesian powers of the$d$-regular graphs for which the lexicographic order yields an optimal order and$\delta _{G}(i)\leq \frac{d}{2}$for$i=0, 1, \ldots, \lfloor \frac{|G|-1}{2}\rfloor$. Our result improves some previous results about$c\lambda _{k}$of Hamming graphs by Yang et al. (2023), and$\lambda _{h}$of the Cartesian powers of the complete graph$K_{4}$by Tian et al. (2022).

With the growing role of multiprocessor systems in big data, artificial intelligence, as well as cloud computing and high-performance computing, the expansion in system scale and complexity has inevitably led to an increase in processor failures (or faults). To enhance the system’s fault diagnosis capability, a novel approach termed$t/s$-diagnosis has been proposed timely. In this article, we delve into the relationship between a general network’s component connectivity and$t/s$-diagnosability under the MM* diagnostic model, and subsequently apply the metric to a variety of networks, including bubble sort graphs, complete cubic networks, hierarchical hypercubes, and generalized exchanged hypercubes. To detect all faulty nodes, we propose the largest connected component under MM* model (LCC-MM*) algorithm along with the analysis of time complexity. In addition, we evaluate the$t/s$-diagnosability of a variety of networks, accompanied by contrasting$t/s$-diagnosability with other conditional diagnosabilities under the MM* diagnostic model. Meanwhile, we conduct experiments on real data to assess the effectiveness and performance of the LCC-MM* algorithm.

The$(f_{1},f_{2})$-bounded symmetric comparison ($(f_{1}, f_{2})$-BSC) model, proposed by Fuhrman and Nussbaumer in 1996, is a hybrid of the symmetric comparison model and asymmetric one, which assumes that at most$f_{1}$processors fail while the upper threshold of faulty processors producing identical outcomes is$f_{2}$. Based on the$(f_{1},f_{2})$-BSC model, a novel model, abbreviated as the$f$-BSC model, is proposed by dropping the restriction on$f_{1}$but highlighting the hypothesis on maximum number of faulty processors producing identical outcomes is$f$. As a generalization of this model, a variant of MM$^*$model abbreviated as the$f$-BMM$^*$model is proposed by adding an upper threshold$f$to the number of faulty processors producing identical comparison outcomes, which are executed by a faulty comparator on two faulty neighbouring processors. Under this restriction, fewer possible syndromes are generated and therefore faulty processors can be diagnosed faster and more accurately. Subsequently, we present diverse characterizations regarding system-level diagnosis under the two new models. Moreover, we further establish the metric correlation between$g$-good-neighbor ($g$-GN) diagnosability under$f$-BMM$^*$model and$R^{g}$-connectivity of general networks. Finally, the$g$-GN diagnosabilities under$f$-BMM$^*$model are characterized among five preeminent interconnection networks.

Abstract Multiprocessor systems play a significant role in big data era. As the probability of presence of processor failures in a multiprocessor system raises with the increase of the system scale, the effect of processor failure is worthy of quantifying. The subsystem reliability of a multiprocessor system is the probability that a fault-free subsystem of certain size still operate with the rise of individual faults. In this work, we employ the probabilistic fault model and the Principle of Inclusion-Exclusion (PIE) to establish the approximation and upper bound on the subsystem reliability of the cactus-based networks through decomposition into $(n-1)$-dimensional subsystems by fixing one position-pair. Numerical simulations show that the upper bound derived in this way is close to the approximation of the accurate subsystem reliability.

Abstract Motivated by a multitude of practical applications, many distinct vulnerability parameters of multiprocessor systems have been explored. Traditional connectivity and diagnosability are undoubtedly the most well investigated of these metrics, but often fail to capture the most subtle differences of a multiprocessor system. Subsequently, it is necessary to take into account the minimum degree of components, the size of components or the number of components. However, the structure of the components is ignored in these circumstances. In this work, we propose a novel diagnostic strategy based on cyclic connectivity, namely the cyclic diagnosability. The cyclic diagnosability, denoted by $ct(G)$, is the maximum size of the faulty vertex set $F$ of $G$ such that the self-diagnosable system $G$ can identify all the vertices in $F$ under the condition that at least two connected components of $G-F$ contain a cycle. Furthermore, we investigate the cyclic diagnosability of hypercube $Q_{n}$ under the PMC model and the MM* model, and show that $ct(Q_{n})=5n-10$ for $n\geq 7$.

Assessment on the reliability of interconnection networks plays a significance role in designing and maintaining interconnection networks. The conditional$h$-edge connectivity$\lambda ^{h}$, the$h$-average degree edge connectivity$\overline{\lambda ^{h}}$, and the$g$-extra edge connectivity$\lambda _{g}$are three considerable indicators for assessment of the reliability of interconnection networks, which can maximally improve the real fault tolerability of interconnection networks. In this article, we obtain the relationship between$\lambda ^{h}$(respectively,$\overline{\lambda ^{h}}$) and$\lambda _{g}$of graphs. Applying this newly established relationship, we obtain$\lambda ^{h}$(respectively,$\overline{\lambda ^{h}}$) of some famous interconnection networks, including 3-ary$n$-cubes, augmented cubes, and enhanced hypercubes. That is, we show that$\begin{aligned} \lambda ^{h}(\overline{\lambda ^{h}})(Q_{n}^{3})\!=\! \left\lbrace \begin{array}{@{}ll@{}}(2n-h)3^{\frac{h}{2}}, \ \ h\ \text{is even, } 0\leq h\leq 2n-2;\\ (4n \!-\! 2h)3^{\frac{h-1}{2}}, \ h\ \text{is odd, } 0\leq h\leq 2n \!-\! 3; \end{array} \right. \end{aligned}$when$k\ne 2$,$ \lambda ^{h}(\overline{\lambda ^{h}})(Q_{n,k})= \left\lbrace \begin{array}{@{}ll@{}}(n+1-h)2^{h}, \ 0\leq h\leq n-k;\\ (n+1-h)2^{h-1}, \ n\!-\!k \!+\! 2 \leq h\leq n; \end{array} \right. $when$k= 2$,$ \lambda ^{h}(\overline{\lambda ^{h}})(Q_{n,k})= \left\lbrace \begin{array}{@{}ll@{}}(n+1-h)2^{h}, \ 0\leq h\leq n-3;\\ 2^{n-1}, \ h= n-2, n-1; \end{array} \right. $and$\lambda ^{h}(AQ_{n})=\overline{\lambda ^{h}}(AQ_{n})=(n-\frac{h+1}{2})2^{\frac{h+3}{2}}$for$h$is odd within the range$1\leq h\leq 2n-3$. In particular, these results extend the previous results in [J. Supercomput.2022, 5: 6739-6751] and [Inform. Process. Lett.2008, 106: 59-63] and also solve positively a conjecture presented by Shinde and Borse [J. Interconnect. Netw.2020, 20: 2050013].

The reliability of interconnection network ordinarily is measured by two significant indexes, namely, connectivity and diagnosability. The qualitative and quantitative reliability analysis relies on the choice of an appropriate mathematical modeling and assumptions consistent with the actual situation. The cyclic connectivity is a well-established index to evaluate the reliability of interconnection network. For a network$\mathbb{G}$, we use$\kappa _{c}(\mathbb{G})$to denote cyclic connectivity of$\mathbb{G}$, which is the minimum size of the node cut set$D$such that$\mathbb{G}-D$is disconnected and at least two of its components have cycles. Based on the cyclic connectivity, cyclic diagnosability ($ct(\mathbb{G})$) is proposed to measure the self-diagnostic capability of the networks. Up to this day, the cyclic connectivity of some special networks has been determined successfully, but the cyclic diagnosability of a great deal of networks is still up in the air. In this work, we investigate the measurable relationship between cyclic connectivity and 2-good connectivity under certain restrictions. Furthermore, we characterize the cyclic diagnosability of a class of networks in terms of character commonality of the networks. To be more specific, we show that$ct(\mathbb{G})=\kappa _{c}(\mathbb{G})+(l-k)$under the PMC model (PMC-M) and the MM$^\ast$model (MM$^\ast$-M), where$l$is the regular degree of network and$l\geq 3, 1\leq k< l$are constant. Then, we directly determine the cyclic diagnosability of hypercubes, locally twisted cubes, and alternating group networks. Finally, we compare the cyclic diagnosability of the network with other kinds of restricted diagnosabilities. The results show that cyclic diagnosability has excellent self-diagnostic capability.

Abstract As a fundamental metric, the connectivity to assess fault tolerance and reliability of interconnection networks has been extensively explored. However, classical connectivity is not very effective at evaluating large-scale networking systems. To overcome this deficiency, two new indices, cluster connectivity and super cluster connectivity, have been proposed to characterize the robustness of interconnection networks. This paper focuses on investigating $\mathcal{H} (\mathcal{H}^{*})$-cluster connectivity and super $\mathcal{H} (\mathcal{H}^{*})$-connectivity of composition graph $DQ_{n}$, based on disc-ring and hypercube, for $\mathcal{H}\in \{K_{1,r}\ |\ 0\leq r\leq n+1\}$, respectively. In detail, we show that $\kappa (DQ_{n}|K_{1,1} (K_{1,1}^{*}))=\kappa ^{\prime}(DQ_{n}|K_{1,1}(K_{1,1}^{*})) =n+1 (n\geq 3)$, $\kappa (DQ_{n}|K_{1,r}(K_{1,r}^{*})) =\left\lceil \frac{n}{2}\right\rceil +1 (2\leq r\leq 4)$ for $n\geq 3$, $\kappa ^{\prime}(DQ_{n}|K_{1}(K_{1}^{*})) =\kappa ^{\prime}(DQ_{n})=2n (n\geq 3)$, and for $2\leq r\leq 3$ and $k\geq 2$, $$\begin{align*} \kappa^{\prime}(DQ_{n}|K_{1,r}(K_{1,r}^{*}))=\left\{\begin{array}{@{}ll} n+1, & if\ n=2k+1; \\ n, & if\ n=2k. \end{array}\right. \end{align*}$$As by-products, we show that DQcube is super $K_{1,r}-\ (K_{1,r}^{*}-)$connected $(2\leq r\leq 3)$, and derive the 4-extra connectivity of DQcube $\kappa _{4}(DQ_{n}) = 5n-9 (n\geq 4)$.

Intermittent faults are common in daily life and industrial manufacture, which have been drawing much attention from both academia and industry. In practice, intermittent faults will pose a great threat to system performance and equipment safety. Because of the randomness and unpredictability of intermittent faults, it is a great challenge to diagnose them. The fault diagnosis strategy under system-level diagnostic model plays a very important role in measuring the endogenous network security without prior knowledge, which can significantly enhance the self-diagnosing capability of network. However, as the networks become large-scale and complicated, the fault diagnosis using full syndromes from a system-level diagnostic model seems to reach its bottleneck. In this article, we first determine that the intermittent fault diagnosability of a general$r$-regular network$G$under comparison model is$(t^{\text{Intermittent}}(G))^{M}=r-2$. This results can be directly applied to 18 well-known networks. Then, we propose a reliable neural network enabled intermittent fault diagnosis algorithm RNNIFDCom to solve the problem of fault identification with partial syndromes for a general$r$-regular network$G$under comparison model. Finally, we implement our proposed algorithm RNNIFDCom in different networks and analyze its performance under different number of faulty nodes in terms of true positive rate, true negative rate, false positive rate, and false negative rate. The experimental results verify the theoretical results and show the advantage of our proposed algorithm RNNIFDCom.

Abstract For the multiprocessor systems modeled by interconnection networks, one of the important properties is the characterization of fault tolerability. Connectivity, as an important parameter to evaluate fault tolerability, has witnessed research achievements. To make the evaluation more practical, conditional connectivity has been promisingly proposed. As one kind of conditional connectivity, $h$-restricted connectivity of a connected graph $G$, denoted by $\kappa ^h (G)$, is defined as the cardinality of the minimum vertex cut set $F$ such that $\delta (G-F)\geq h$. In this paper, we establish a universally $h$-restricted connectivity for a class of hypercube-based compound networks, in which the well-known networks, such as hierarchical cubic network $HCN(n, n)$ and its generalization complete cubic network $CCN(n)$, are involved.

With the emergence of the Big Data era, as multiprocessor systems consisting of multiple processors play a vital role in big data analytics, we are prompted to explore the qualitative and quantitative metric to characterize the reliability of the systems. As the size of the multiprocessor systems grows, the probability of the occurrence of failing processors increases. One metric of the macroscopic reliability of a system is the measure of the collective effect when its subsystems are out of function. The subsystem reliability of a system is the quantitative metric that a fault-free subsystem of specific size is operational as before with the occurrence of individual faults. Although some networks have the same order and similar topologies, there are differences in their subsystem reliabilities. In this work, we focus on the comparison of two distinct topologies of$k$-ary$n$-cube networks with the same order and calculate the robustness of reliability bounds of$k$-ary$n$-cube networks. We analytically show that the subsystem reliability is negatively correlated with the dimension$n$, even if two subsystems of$Q_{n}^{k}$are of the same order. That is, the smaller$n$is, the larger subsystem reliability of$Q_{n}^{k}$will be. This work provides a theoretical methodology to choose the more dependable topology of$k$-ary$n$-cube networks with the same order. Finally, we apply some numerical simulations to validate the results we established.

Reliability evaluation of multiprocessor systems is of great significance to the design and maintenance of these systems. As two generalizations of traditional edge connectivity, extra edge connectivity and component edge connectivity are two important parameters to evaluate the fault-tolerant capability of multiprocessor systems. Fast identifying the extra edge connectivity and the component edge connectivity of high order remains a scientific problem for many useful multiprocessor systems. In this article, we determine the$h$-extra edge connectivity of the 3-ary$n$-cube$Q_n^3$for$h\in [1, \frac{3^n-1}{2}]$. Specifically, we divide the interval$[1, \frac{3^n-1}{2}]$into some subintervals and characterize the monotonicity of$\lambda _h(Q_n^3)$in these subintervals and then deduce a recursive closed formula of$\lambda _h(Q_n^3)$. Based on this formula, an efficient algorithm with complexity$O(\log _3\,N)$is designed to determine the exact values of$h$-extra edge connectivity of the 3-ary$n$-cube$Q_n^3$for$h\in [1, \frac{3^n-1}{2}]$completely. Moreover, we also determine the$g$-component edge connectivity of the 3-ary$n$-cube$Q_n^3(n\geq 6$) for$1\leq g\leq 3^{\lceil \frac{n}{2}\rceil }$.

Abstract Diagnosability is an important metric to fault tolerance and reliability for multiprocessor systems. However, plenty of research on fault diagnosability focuses on node failure. In practical scenario, not only node failures take place but also link malfunctions may arise. In this work, we investigate the diagnosability of general regular networks with failing nodes as well as missing malfunctional links. Let $S$ be a set of the missing links and broken-down nodes. We first prove that the diagnosability of the survival graph $G\setminus S$ persists $\delta (G\setminus S)$ under the PMC model (Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput., EC-16, 848–854) for a $t$-regular and $t$-connected triangle-free network $G$ subject to $|S|\leq t-1$ and $|V(G)|\geq 3t-2$ ($t\geq 3$). Furthermore, we determine the diagnosability of $G\setminus S$ for some kinds of extensively explored $t$-regular networks with triangles subject to $|S|\leq t-1$ ($t\geq 3$).

Connectivity is a classic metric to evaluate reliability of multiprocessor system under the circumstances of processor failures. Based on connectivity, more refined quantitative indicators for fault tolerance of multiprocessor system have been extensively explored. The g-component connectivity of a graph G, denoted by cκg(G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least g-components. So far, the values of the g-component (edge) connectivity of special networks with small g have been extensively investigated. For general graphs, the results of the g-component connectivity are very few. In this paper, we propose some lower and upper bounds for the g-component connectivity along with their sharpness, and then suggest some characterization of trees and general graphs with given g-component connectivity. Furthermore, we fix some related extremal problems.

Abstract In this paper, we propose a new digragh model for system level fault diagnosis, which is called the $(f_1,f_{2})$-bounded Preparata–Metze–Chien (PMC) model (shortly, $(f_1,f_{2})$-BPMC). The $(f_1,f_{2})$-BPMC model projects a system such that the number of faulty processors that test faulty processors with the test results $0$ does not exceed $f_{2}$$(f_2\leq f_{1})$ provided that the upper bound on the number of faulty processors is $f_{1}$. This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran. Electron. Comput.,EC-16, 848–854) and Barsi–Grandoni–Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput.C-25, 585–593). Then we present some characterizations for one-step diagnosibility under the $(f_1,f_{2})$-bounded PMC model, and determine the diagnosabilities of some special regular networks. Meanwhile, we establish the characterizations of $f_1/(n-1)$-diagnosability and three configurations of $f_1/(n-1)$-diagnosable system under the $(f_1,f_{2})$-BPMC model.

Fault tolerance plays an important role in the interconnection networks, where permanent and intermittent faults are two kinds of fault situations. Permanent fault diagnosabilities of regular networks have been proposed widely while the intermittent fault diagnosabilities are also noteworthy. In this paper, we give a sufficient and necessary condition for k-regular k-connected graph Gn to be ti-diagnosable without repair in intermittent fault pattern. Detailly, we show that the intermittent fault diagnosability of Gn under the PMC model is k−⌈g−12⌉−2⁠, where g is the maximum number of common neighbors for any two distinct vertices. As applications, intermittent fault diagnosabilities of many famous networks are explored.

As a critical parameter in evaluating the reliability of a multiprocessor system when processors malfunction, the \boldmath h-extra connectivity (h-EC) of a multiprocessor system modeled by a graph G, denoted by κo(h)(G), is an h-extra vertex-cut with minimum cardinality. Both of the h-extra conditional diagnosability (h-ECD) and the t/h-diagnosability of the multiprocessor system are vital to tolerate and diagnose faulty processors. These two parameters rely on the resolving of hEC. For the multiprocessor system based on star graph Sn, we show that the 5-EC κo(5)(Sn) of Sn(n ≥ 5) is 6n - 18. As a by-product, we present a novel proof of κo(2)(Sn) = 3n - 7 (resp., κo(4)(Sn) = 5n - 14) by relaxing the restriction n ≥ 10 (resp., n ≥ 7) to n ≥ 5 (resp., n ≥ 5). Furthermore, we determine that the h-ECD of Sn(n ≥ 5) under the preparata, metze, and chien (PMC) model is (h + 1)n - 2h - 1 for 1 ≤ h ≤ 3 and (h + 1)n - 3h + 2 for 4 ≤ h ≤ 5. In addition, we show that Snis [(h + 1)n - 4h + 2]/h-diagnosable for 4 ≤ h ≤ 5, which extends the result that Snis [(h + 1)n - 3h - 1]/h-diagnosable for 1 ≤ h ≤ 3 by [Zhou et al. “The t/k-diagnosability of star graph networks,” IEEE Trans. Comput., vol. 64, no. 2, pp. 547-555, Feb. 2015].

In the cloud computing environment with massive information services and decision-making resources, the accuracy and reliability of information are more important than previous single closed systems. Therefore, ensuring the reliability of information and the stable operation of the system are the core problems in the research fields such as the Internet Plus and the Internet of Things. The connectivity and diagnosability are two important measures for the fault tolerance of multiprocessor systems. The g -good-neighbor conditional connectivity ( Rg -connectivity) is the minimum number of nodes that make the graph disconnected, and each node has at least g neighbors in every remaining component. The g -good-neighbor conditional diagnosability ( g -GNCD) is the maximum number of faulty processors that has been correctly identified in a system, and any fault-free processor has no less than g fault-free neighbors. Exchanged X -cubes are a class of irregular networks, obtained by deleting links from hypercubes and some variant networks of hypercubes ( X -cubes). They not only combine the advantages of X -cubes but also reduce the interconnection complexity. Exchanged X -cubes classify its nodes into two different classes clusters with a unique connecting rule. In this paper, we propose the generalized exchanged X -cubes framework so that architecture can be constructed by different connecting rules. Furthermore, we study the Rg -connectivity and g -GNCD of generalized exchanged X -cubes under the PMC and MM ∗ models. As applications, the Rg -connectivity and g -GNCD of generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally generalized exchanged twisted cubes are determined, respectively.

For a connected graph G=(V(G),E(G))⁠, a subset F⊂V(G) is called an Rk-vertex-cut if G−F is disconnected and each vertex u∈V(G)−F has at least k neighbors in G−F⁠. The cardinality of a minimum Rk-vertex-cut of G is the Rk-vertex-connectivity and is denoted by κk(G)⁠. The conditional connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study R1-vertex-connectivity and R2-vertex-connectivity of Cayley graphs generated by 2-trees T2,n⁠, which are denoted by KTn⁠, and show that κ1(KTn)=4n−8 for n≥4⁠; κ2(KTn)=8n−22 for n≥6⁠.

A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n; k)-arrangement graph network An;k. We will show that, under both the PMC model and the comparison model, the An;k's g-good-neighbor conditional diagnosability is [(g + 1)k - g](n - k), which can be several times higher than the An;k's original diagnosability.

Fault tolerance is the ability such that a multiprocessor system operates properly in the event of the failure of some of its components. Latifi et al. [IEEE Trans. Comput. 43 (2) (1994) 218–222] proposed the notion of Rg-connectivity(κg) of a network modeled by graph G such that at least κg vertices in G should be deleted to disconnect the network, and the minimum degree of every connected component is at least g. This paper establishes κg(CCN(n))=(n−g+1)2g(1≤g≤n−2) for n-dimensional complete cubic network CCN(n)⁠. Fault diagnosability is another important metric for evaluating network reliability and availability. In 2012, Peng et al. [Appl. Math. Comput. 218 (21) (2012) 10406–10412] proposed a novel g-good-neighbor (conditional) diagnosability, which tacitly assumes that every fault-free vertex has at least g fault-free neighbors. In view of κg(CCN(n))⁠, we show that the g-good-neighbor diagnosability of the complete cubic network CCN(n) under the PMC model (⁠1≤g≤n−2⁠) and the MM* model (⁠1≤g≤n−2 and n≥4⁠) is (n−g+2)2g−1⁠, respectively.

As the size and complexity of a multiprocessor system increases, reliability evaluation becomes an important issue. The performability of a multiprocessor system heavily depends on the application program and the underlying architecture. In multitasking multiprocessor system, the problem of dynamically assigning a given dimensional subsystem to a special task is considered as a reallocation in the presence of node and/or link failures. This paper takes the generalization of star graph, (n, k)-star graph, as an empirical object. In order to measure the reliability of (n, k)star graph, the analytical model introduces mean time to failure (MTTF) to show the time that the appearance of a certain number of faulty Sn-1,k-1costs. The higher the MTTF, the better the robustness. So, the way to evaluate the robustness of an (n, k)-star is to count how much the MTTF is. In fact, an (n, k)-star can be partitioned along any dimension (except the first one) with corresponding identification code. So, we will explore the reliability of (n, k)-star graph when it is partitioned along any dimension (except the first one) under node and/or link fault model. Comparisons among the simulation results under two partitioning models reveal that the MTTF is higher under liberal partition model, which better reflect the steady state of an interconnection network that can persist when the network is destroyed.

The |$n$|-dimensional burnt pancake network, denoted by |$BP_n$|⁠, originates from the Burnt pancake problem which relates to the construction of networks of parallel processors. In the wake of rapid development of multiprocessor systems, processor fault diagnosis plays an even more important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated. The conditional diagnosability has been widely accepted as a new measure of diagnosability by assuming that any faulty set cannot contain all the neighbors of any node in a multiprocessor system. In this paper, we explore combinatorial properties of burnt pancake networks, and investigate the structural vulnerability as well as extra connectivities. Furthermore, we show that the classic diagnosability and the conditional diagnosability of |$BP_n$| (⁠|$n\geq 4$|⁠) under the Preparata, Metze and Chien model are |$n$| and |$8n-13$|⁠, respectively.

The$t/k$-diagnosis strategy can significantly enhance the system’s self-diagnosing capability at the expense of no more than$k$fault-free processors (vertices) being mistakenly diagnosed as faulty under the PMC model. It is a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis on multiprocessor systems. It can detect up to$t$faulty processors (vertices) which might include at most$k$misdiagnosed processors (vertices), where$k$is typically a small number. In the case$k\ge 1$, to our knowledge, there is no known$t/k$-diagnosis algorithm for general regular networks. In this paper, we first propose a general$t/k$-diagnosis ($k\ge 1$) algorithm for some$m$-regular networks. These$m$-regular networks satisfying some conditions could establish the$t/k$-diagnosis algorithm, say$t/k$-$G$-$DIAG$, to determine the$t/k$-diagnosability. The complexity of this algorithm is only$O(N\log N)$(when$N\ge 2^m$) or$O(Nm)$(when$N< 2^m$) where$N$is the number of vertices in the network. Second, we present a complete proof that the network$G$is actually$t/k$-diagnosable. Finally, we establish the$t/k$-diagnosability ($1\le k\le 3$) of some regular networks, including an$n$-dimensionalalternating group graph, an$n$-dimensionalSplit-Star Network, a$l^n$-hypermeshand an$(n,l)$-star graph, which are well-known interconnection networks proposed for multiprocessor systems.

Connectivity is a classic measure for fault tolerance of a network in the case of vertices failures. Extra connectivity and restricted connectivity are two important indicators of the robustness of a multi-processor system in presence of failing processors. An interconnection network's diagnosability is an important measure of its self-diagnostic capability. The conditional diagnosability is widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbors of any node in a multiprocessor system. In this paper, we analyze the combinatorial properties and fault tolerance ability for the Split-Star Network, denoted by Sn2, a well-known interconnection network proposed for multiprocessor systems, establish the g-extra connectivity, where 1 ≤ g ≤ 3. We also determine the h-restricted connectivity (h = 1; 2), and prove that the conditional diagnosability of Sn2(n ≥ 4) is 6n - 16 under the comparison model, which is about three times of the Sn2's traditional diagnosability. As a product, the strong diagnosability of Sn2is also obtained.

As the cardinality of multiprocessor systems grows, the probability of arising malfunctioning or failing processors in the system is bound to increase. It is then of both practical and theoretical importance to know the reliability of the system as a whole. One metric for a system's overall reliability is the measurement of the collective effect of its subsystems becoming faulty. However, a challenge of this approach is that the subsystems often interact with each other in a complex manner, making the analysis difficult. Wu and Latifi (Int. Sci., vol. 178, pp. 2337-2348, Oct. 2008) proposed two schemes to evaluate the system reliability of the Star graph network under a probabilistic fault model. The first scheme computes the combinatorial probability of subgraphs to obtain an upper-bound on the reliability by considering the intersection of no more than three subgraphs. The second scheme computes an approximate combinatorial probability by completely neglecting the intersection among subgraphs. Recently, Lin et al. have applied this approach to investigate the reliability of the multiprocessor system based on the arrangement graph (IEEE Trans. Rel., vol. 62, no. 2, pp. 807-818, Jun. 2015). In this paper, we extend the above approach by computing both upper- and lower-bounds and considering the difference of the two, to establish the reliability of the (n, k) -Star graph, another extensively studied interconnection network for multiprocessor systems. More specifically, we compute a lower-bound and an upper-bound on the reliability by taking into account the intersection of no more than four or three subgraphs, respectively. The empirical study shows that the upper- and lower-bounds are both very close to the approximate results. Especially, the lower the single-node reliability goes, the closer the approximate reliability is to both lower- and upper-bounds.

Extra connectivity is an important indicator of the robustness of a multiprocessor system in presence of failing processors. The g-extra conditional diagnosability and the t/m-diagnosability are two important diagnostic strategies at system-level that can significantly enhance the system's self-diagnosing capability. The g-extra conditional diagnosability is defined under the assumption that every component of the system removing a set of faulty vertices has more than g vertices. The t/m-diagnosis strategy can detect up to t faulty processors which might include at most m misdiagnosed processors, where m is typically a small integer number. In this paper, we analyze the combinatorial properties and fault tolerant ability for an (n, k)-arrangement graph, denoted by An,k, a well-known interconnection network proposed for multiprocessor systems. We first establish that the An,k's one-extra connectivity is (2k - 1) (n - k) - 1 (k ≥ 3, n ≥ k + 2), two-extra connectivity is (3k - 2)(n - k) - 3 (k ≥ 4, n ≥ k + 2), and three-extra connectivity is (4k - 4)(n - k) - 4 ( k ≥ 4, n ≥ k + 2 or k ≥ 3, n ≥ k + 3), respectively. And then, we address the g-extra conditional diagnosability of An,kunder the PMC model for 1 ≤ g ≤ 3. Finally, we determine that the (n, k)-arrangement graph An,kis [(2k - 1)(n - k) - 1]/1-diagnosable (k ≥ 4, n ≥ k + 2), [(3k - 2)(n - k) - 3]/2-diagnosable (k ≥ 4, n ≥ k + 2), and [(4k - 4)(n - k) - 4]/3-diagnosable (k ≥ 4, n ≥ k + 3) under the PMC model, respectively.

The${{t/k}}$-diagnosis is a diagnostic strategy at system level that can significantly enhance the system’s self-diagnosing capability. It can detect up to${{t}}$faulty processors (or nodes, units) which might include at most${{k}}$misdiagnosed processors, where${ {k}}$is typically a small number. Somani and Peleg (, 1996) claimed that an$n$-dimensional Star Graph (denoted${{S_n}}$), a well-studied interconnection model for multiprocessor systems, is${{((k + 1)n - 3k - 2)/k}}$-diagnosable. Recently, Chen and Liu (, 2012) found counterexamples for the diagnosability obtained in, without further pursuing the cause of the flawed result. In this paper, we provide a new, complete proof that an${\mbi {n}}$-dimensional Star Graph is actually${{((k + 1)n - 3k - 1)/k}}$-diagnosable, where${{1 \leq k \leq 3}}$, and investigate the reason that caused the flawed result in. Based on our newly obtained fault-tolerance properties, we will also outline an${ {O(N \log N)}}$diagnostic algorithm (${ {N = n!}}$is the number of nodes in${{S_n}}$) to locate all (up to${ {(k + 1)n - 3k - 1}}$) faulty processors, among which at most${ {k\, (1 \leq k \leq 3)}}$fault-free processors might be wrongly diagnosed as faulty.

Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3, and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGnis also obtained.

As the size of a multiprocessor computer system grows, the probability of having faulty (i.e., malfunctioning or failing) processors in the system increases. It is then important to quantify how the faults collectively affect the entire system. The reliability of subsystems in a system, defined as the probability that a fault-free subsystem of a certain size still exists when the system has faults, is a measure for the faults' effect on the whole system. It can be used as an indicator of system health. In this paper, we will present two schemes to calculate the reliability of an$(n-1,k-1)$-subgraph in the$(n,k)$-Arrangement Graph$A_{n,k}$, an extensively studied interconnection network proposed for multiprocessor computers. The first scheme will use a probability fault model and the Principle of Inclusion-Exclusion to establish an upper-bound of the reliability, by taking into account the intersection of not more than three subgraphs. The second scheme uses basically the same idea, but completely neglects the intersection among subgraphs to calculate an approximate reliability. The results of the two schemes are compared, and are shown to be in good agreement, especially as the single-node reliability$p$goes low.

SUMMARY With the development of wireless mesh networks (WMNs), fault diagnosis in WMNs is becoming a very challenging task. In this paper, a two‐level scheme for fault diagnosis in WMNs is presented. We partition the network into a two‐level topology architecture where level 1 is composed of mesh clients and level 2 consists of mesh routers. A new comparison approach is introduced to diagnose the two levels. On the basis of the new comparison approach, every node in WMNs can be diagnosed either as fault‐free or faulty. Our protocol assumes that the WMN's topology may change during the testing phase and utilize the shortest path spanning tree, which is constructed along with the process of fault diagnosis, to disseminate local messages and global messages in WMNs. The proposed model is only for static fault circumstances. We provide the analysis of correctness, communication complexity, and time complexity of our protocol, and the comparison between our protocol and others through both theoretical proof and practical simulation. The analysis shows that our model has significant advantages over other existing models. Copyright © 2012 John Wiley & Sons, Ltd.

The existence of parallel node-disjoint paths between any pair of nodes is a desirable property of interconnection networks, because such paths allow tolerance to node and/or link failures along some of the paths, without causing disconnection. Additionally, node-disjoint paths support high-throughput communication via the concurrent transmission of parts of a message. We characterize maximum-sized families of parallel paths between any two nodes of alternating group networks. More specifically, we establish that in a given alternating group network AN n , there exist n−1 parallel paths (the maximum possible, given the node degree of n−1) between any pair of nodes. Furthermore, we demonstrate that these parallel paths are optimal or near-optimal, in the sense of their lengths exceeding the internode distance by no more than four. We also show that the wide diameter of AN n is at most one unit greater than the known lower bound D+1, where D is the network diameter.

In evaluating the fault tolerance of an network structure, it is essential to estimate the order of a maximal connected component of this network provided the faulty vertices may break its connectedness, and it is crucial to local and to replace the faulty processors to maintain systempsilas high reliability. The fault diagnosis is the process of identifying fault processors in a system through testing. The conditional diagnosis requires that for each processor v in a system, all the processors that are directly connected to v do not fail at the same time. In this paper, the conditional diagnosability of the twisted cubes TQn under the comparison diagnosis model is 3n-5 when n>6. Hence the conditional diagnosability of TQn is three times larger than its classical diagnosability.