Narrow Results

The diagnosability is a prominent parameter to estimate the fault diagnosis capability of multiprocessor systems, which is the maximum number of faulty processors that can be identified by the system. Compared to traditional diagnosability, strong diagnosability proposed by Lai et al. [16] is a more pinpoint term for gauging multiprocessor systems’ reliability. A system is strongly $t$-diagnosable if it is $t$-diagnosable and can attain $(t+1)$-diagnosability, excepting certain circumstance in which all neighbors of some processor are faulty. In this paper, we obtain the strong diagnosability of regular networks as well as connected networks subject to certain circumstances under the PMC model, respectively. The previous result in Hsieh et al. [7] is extended.

Problem diagnosis in large distributed computer systems and networks is a challenging task that requires fast and accurate inferences from huge volumes of data. In this paper, the PMC diagnostic model is considered, based on the diagnostic approach of end-to-end probing technology. A probe is a test transaction whose outcome depends on some of the system's components; diagnosis is performed by selecting appropriate probes and analyzing the results. In the PMC model, every computer can execute a probe to test a dedicated system's components. Furthermore, any test result reported by a faulty probe station is unreliable and the test result reported by fault-free probe station is always correct. The aim of the diagnosis is to locate all faulty components in the system based on collection of the test results. A dual-cube DC(n) is an (n + 1)-regular spanning subgraph of a (2n + 1)-dimensional hypercube. It uses n-dimensional hypercubes as building blocks and returns the main desirable properties of the hypercube so that it is suitable as a topology for distributed systems. In this paper, we first show that the diagnosability of DC(n) is n + 1 and then show that adaptive diagnosis is possible using at most 2²ⁿ⁺¹ + n tests for a 2²ⁿ⁺¹-node distributed system modeled by dual-cubes DC(n) in which at most n + 1 processes are faulty. Furthermore, we propose an adaptive diagnostic algorithm for the DC(n) and show that it diagnoses the DC(n) in three testing rounds and at most 2²ⁿ⁺¹ + O(n³) tests, where each node is scheduled for at most one test in each round.

The processor failures in a multiprocessor system have a negative impact on its distributed computing efficiency. Because of the rapid expansion of multiprocessor systems, the importance of fault diagnosis is becoming increasingly prominent. The $h$-component diagnosability of $G$, denoted by $c{t}_h(G)$, is the maximum number of nodes of the faulty set $F$ that is correctly identified in a system, and the number of components in $G-F$ is at least $h$. In this paper, we determine the $(h+1)$-component diagnosability of general networks under the PMC model and MM${}^{\ast }$ model. As applications, the component diagnosability is explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, hierarchical hypercubes, Cayley graphs generated by transposition trees (except star graphs), and DQcube as well. Furthermore, we provide some comparison results between the component diagnosability and other fault diagnosabilities.

Processor fault diagnosis is intended to identify faulty processors of a multicomputer system, guaranteeing its high reliability and availability. The $g$-good-neighbor conditional diagnosability is a novel fault diagnosis method for various networks. Under the PMC model and comparison model, the $g$-good-neighbor conditional diagnosabilities of hypermesh optical interconnection networks are determined, respectively. Directly applying the results, the $g$-good-neighbor conditional diagnosabilities of hypercubes are derived under the PMC and comparison models.

Multiprocessor systems are commonly deployed for big data analysis because of evolution in technologies such as cloud computing, IoT, social network and so on. Reliability evaluation is of significant importance for maintenance and improvement of fault tolerance for multiprocessor systems, and system-level diagnosis is a primary strategy to identify the faulty processors in the systems. In this paper, we first determine the $g$-good-neighbor connectivity of the $n$-dimensional Bicube-based multiprocessor system $B{Q}_n$, a novel variant of hypercube. Besides, we establish the $g$-good-neighbor diagnosability of the Bicube-based multiprocessor system $B{Q}_n$ under the PMC and MM* models.

Let t_c(G) and t_g(G) be the conditional diagnosability and g-good-neighbor diagnosability, respectively, of a graph G. The notion of the g-good-neighbor conditional diagnosability is less restrictive as compared with that of the conditional diagnosability in general. Particularly, the conditional faulty set notion requires that, any vertex, faulty or not, have at least one non-faulty neighbor; while the 1-good-neighbor faulty only requires that a non-faulty vertex have at least one non-faulty neighbor. Compared with conditional diagnosability, g-good-neighbor diagnosability is interesting since it characterizes a stronger tolerance capability. In this paper, we investigate the equal relation between t₁(BH_n) and t_c(BH_n) for the balanced hypercubes BH_n. That is $t_1(B{H}_n)=t_c(B{H}_n)=4n\text{ - }3$ for $n\ge 2$ under the PMC model and $t_1(B{H}_n)=t_c(B{H}_n)=4n\text{ - }4$ for $n\ge 2$ under the MM model; Furthermore, the 2-good-neighbor diagnosability t₂(BH_n) = 4_n − 1 for n ≥ 2 under the PMC model and the MM model is obtained.

A system is t/t-diagnosable if, provided the number of faulty processor is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistake as a faulty one. The pessimistic diagnosability of a system G, denoted by $t_p(G)$, is the maximal number of faulty processors so that the system G is t/t-diagnosable. The augmented cube $A{Q}_n$, proposed by Choudum and Sunitha [Networks 40 (2) (2002) 71–84], has many attractive properties such as regularity, strong connectivity and symmetry. In this paper, we determine the pessimistic diagnosability of the n-dimensional augmented cube $A{Q}_n$ and prove that $t_p(A{Q}_n)=4n-8$ for $n\ge 5$.

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. In this paper, we study the 1-good-neighbor conditional diagnosabilities of some general k-regular k-connected graphs G under the PMC model and the MM* model. The main result $t_1(G)=2k-\mathcal{l}-1$ under some conditions is obtained, where l is the maximum number of common neighbors between any two adjacent vertices in G. Moreover, the following results are derived: $t_1(H{S}_n)=2n-1$ for the hierarchical star networks, $t_1(X_n)=2n-1$ for the BC networks, $t_1(A{G}_n)=4n-10$ for the alternating group graphs $A{G}_n$.

The g-extra connectivity of a multiprocessor system modeled by a graph G, denoted by ${\kappa }_o^{(g)}$ (G), is the minimum number of removed vertices such that the network is disconnected and each residual component has no less than g + 1 vertices. The t/k-diagnosis strategy can detect up to t faulty processors which might include at most k misdiagnosed processors. These two parameters are important to measure the fault tolerant ability of a multiprocessor system. The extra connectivity and t/k-diagnosability of many well-known networks have been investigated extensively and independently. However, the general relationship between the extra connectivity and the t/k-diagnosability of general regular networks has not been established. In this paper, we explore the relationship between the k-extra connectivity and t/k-diagnosability for regular networks under the classic PMC diagnostic model. More specifically, we derive the relationship between 1-extra connectivity and pessimistic diagnosability for regular networks. Furthermore, the t/k-diagnosability and pessimistic diagnosability of some networks, including star network, BC networks, Cayley graphs generated by transposition trees etc., are determined.

The diagnosability of a multiprocessor system is of great significance in measuring the reliability and faulty tolerance of interconnection networks. In this paper, we firstly study the diagnosability of the $n$-dimensional folded hypercube $F{Q}_n(n\ge 4)$ under the PMC model. We prove that $F{Q}_n-F$ keeps the strong local diagnosability property even if it has the set $F$ of $(n-1)$ faulty edges and $n-1$ is maximum number of faulty edges. Secondly, we study the diagnosability of $F{Q}_n$$(n\ge 5$ and $n$ is odd) with conditional faulty edges under the PMC model. We prove that $F{Q}_n-F$ keeps strong local diagnosability property even if it has the set $F$ of $(3n-4)$ faulty edges, provided that each vertex of $F{Q}_n-F$ is incident with at least two fault-free edges, where $3n-4$ is maximum number of faulty edges. Finally, we prove that $F{Q}_n-F$ keeps strong local diagnosability property no matter how many edges are faulty, provided that each vertex of $F{Q}_n-F$ is incident with at least three fault-free edges.

Connectivity is an important measure parameter to evaluate the fault tolerance of networks. With the continuous expansion of networks scale, it is inevitable that the processor fails. Once the processor fails, the information processed by the failed processor will be unreliable, which may cause fatal consequences. Therefore, it is of great significance to study the connectivity and diagnosability of networks. In this paper, we establish that the $(r+1)$-component connectivity of DQcube is $c{\kappa }_{r+1}(DQ(m,d,n))=-\frac{1}{2}{r}^2+(n+\frac{1}{2})r+1$, where $n\ge 2$ and $1\le r\le n$. Furthermore, we determine that the $(r+1)$-component diagnosability of DQcube is $c{t}_{r+1}(DQ(m,d,n))=-\frac{1}{2}{r}^2+(n-\frac{1}{2})r+n+1$ under the PMC model and the MM* model, where $n\ge 3$ and $1\le r\le n-3$.

Fault tolerance is critical to reliability analysis of interconnection networks since the vulnerability of component failure increases with the growth of network scale. Extra connectivity and extra diagnosability are two decisive indicators of the ability of parallel and distributed systems to tolerate and diagnose faulty nodes. This paper mainly establishes the $3$-extra connectivity and $3$-extra diagnosability of augmented $3$-ary $n$-cubes $A{Q}_{n,3}$, which is a generalization of $k$-ary $n$-cubes and augmented cubes. In addition, we explore the $3$-extra diagnosis algorithm of $A{Q}_{n,3}$ under the MM* model.

In [1], Elhadef and Ayeb first applied genetic algorithms to system-level diagnosis, in which the fitness function is calculated by comparing the given syndrome with the syndrome randomly produced by the currently guessed fault set. One demerit of the above algorithm lies in the fact that the related fitness function takes only one from many possible syndromes for consideration, leading to the much likely loss of real fault set. In the paper, we first propose some equations for for adjacent units which are compatible with the given syndrome under PMC model. Based on this, we bring forth a suitable fitness function of genetic algorithm for the fault diagnosis of t-diagnosable system. Then, through theoretical analysis, our new fitness function is much superior to the one proposed by Elhadef and Ayeb.

This article has mainly analyzed the system diagnosis PMC model symptom characteristic, obtains it satisfied the condition, proposes the new algorithm. This algorithm had the high parallelism and the development of neural network has realized the algorithm possibility with the analogous circuit, and has carried on the simulation confirmation.