Search

Reliability of a multiprocessor system becomes an important issue for parallel computing. Component diagnosability and component connectivity of a graph play crucial roles in assessing the vulnerability of an interconnection network, which are two significant indicators for the reliability and fault tolerance of a multiprocessor system. Until now, only a little knowledge of results have been known on |$r$| -component diagnosability and |$r$| -component connectivity. In this paper, we first propose the |$r$| -component diagnosability of |$n$| -dimensional alternating group graph |$AG_{n}$| under PMC model. And then we promote our research on |$AG_{n}$| by a fairly good construction for general |$r$| -component connectivity of |$AG_{n}$|⁠ , where |$6\leq r\leq n-1$|⁠. The theoretical analysis and simulation show that the general |$r$| -component connectivity of |$AG_{n}$| is larger than those of |$Q_{n}$|⁠ , |$D_n$| and |$FQ_{n}$|⁠. [ABSTRACT FROM AUTHOR]

A human contact network (HCN) consists of individuals moving around and interacting with each other. In HCN, it is essential to detect malicious users who break the data delivery through terminating the data delivery or tampering with the data. Since malicious users will pay more but gain less when breaking the data delivery of opportunistic contacts, we focus on the non-opportunistic contacts that occur more frequently and stably. It is observed that people contact with each other more frequently if they have more social features in common. In this paper, we build up topology structure for HCN based on social features, and propose a graph theoretical comparison detection model to perform malicious users detection. Then we present an adaptive detection scheme based on Hamiltonian cycle decomposition. Also, we define comparison-0-string and comparison-1-string to improve the detection efficiency. Moreover, we perform scenario simulations on real data to realize the detected process of malicious users. Experiments show that, when the number of malicious users is bounded by the dimension of HCN, our scheme has a detection rate of 100% with both false positive rate and false negative rate being 0%, and the running cost is also very low when compared to baseline approaches. When the number of malicious users exceeds the bound, the detection rate of our scheme decreases slowly, while the false positive rate and false negative rate increase slowly, but they are still better than the baseline approaches. [ABSTRACT FROM AUTHOR]

For interconnection network losing processors, it is considerable to calculate the number of vertices in the maximal component in the surviving network. Moreover, the component connectivity is a significant indicator for reliability of a network in the presence of failing processors. In this article, we first prove that when a set $M$ of at most $3n-7$ processors is deleted from an $n$ -star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-3$. We then prove that when a set $M$ of at most $4n-9$ processors is deleted from an $n$ -star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-5$. Finally, we also calculate the $r$ -component connectivity of the $n$ -star graph for $2\leq r\leq 5$. [ABSTRACT FROM AUTHOR]

Cyberspace is not a “vacuum space”, and it is normal that there are inevitable viruses and worms in cyberspace. Cyberspace security threats stem from the problem of endogenous security, which is caused by the incompleteness of theoretical system and technology of the information field itself. Thus it is impossible and unnecessary for us to build an “aseptic” cyberspace. On the contrast, we must focus on improving the “self-immunity” of network. Literally, endogenous security is an endogenous effect from its own structural factors rather than external ones. The $t/k$ t / k -diagnosis strategy plays a very important role in measuring endogenous network security without prior knowledge, which can significantly enhance the self-diagnosing capability of network. As far as we know, few research involves $t/k$ t / k -diagnosis algorithm and $t/k$ t / k -diagnosability of interconnection networks under MM* model. In this article, we propose a fast $f(r,k+1)/k$ f (r , k + 1) / k -diagnosis algorithm of complexity $O(Nr^2)$ O (N r 2) , say $G$ G MIS $k$ k DIAGMM*, for a general $r$ r -regular network $G$ G under MM* model by designing a 0-comparison subgraph $M_0(G)$ M 0 (G) , where $N$ N is the size of $G$ G . We determine that the $t/k$ t / k -diagnosability $(t(G)/k)^M$ (t (G) / k) M of $G$ G under MM* model is $f(r,k+1)$ f (r , k + 1) by $G$ G MIS $k$ k DIAGMM* algorithm. Moreover, we establish the $(t(G)/k)^M$ (t (G) / k) M of some interconnection networks under MM* model, including BC networks, $(n,l)$ (n , l) -star graph networks, and data center network DCells. Finally, we compare $(t(G)/k)^M$ (t (G) / k) M with diagnosability, conditional diagnosability, pessimistic diagnosability, extra diagnosability, and good-neighbor diagnosability under MM* model. It can be seen that $(t(G)/k)^M$ (t (G) / k) M is greater than other fault diagnosabilities in most cases. [ABSTRACT FROM AUTHOR]

As the size of a multiprocessor system grows, the probability that faults occur in this system increases. One measure of the reliability of a multiprocessor system is the probability that a fault-free subsystem of a certain size still exists with the presence of individual faults. In this paper, we use the probabilistic fault model to establish the subgraph reliability for |$AG_n$|⁠ , the |$n$| -dimensional alternating group graph. More precisely, we first analyze the probability |$R_n^{n-1}(p)$| that at least one subgraph with dimension |$n-1$| is fault-free in |$AG_n$|⁠ , when given a uniform probability of a single vertex being fault-free. Since subgraphs of |$AG_n$| intersect in rather complicated manners, we resort to the principle of inclusion–exclusion by considering intersections of up to five subgraphs and obtain an upper bound of the probability. Then we consider the probabilistic fault model when the probability of a single vertex being fault-free is nonuniform, and we show that the upper bound under these two models is very close to the lower bound obtained in a previous result, and it is better than the upper bound deduced from that of the arrangement graph, which means that the upper bound we obtained is very tight. [ABSTRACT FROM AUTHOR]

The $t/k$ t / k -diagnosability and $h$ h -extra connectivity are regarded as two important indicators to improve the network reliability. The $t/k$ t / k -diagnosis strategy can significantly improve the self-diagnosing capability of a network at the expense of no more than $k$ k fault-free nodes being mistakenly diagnosed as faulty. The $h$ h -extra connectivity can tremendously improve the real fault tolerability of a network by insuring that each remaining component has no fewer than $h+1$ h + 1 nodes. However, there is few result on the inherent relationship between these two indicators. In this article, we investigate the reason that caused the serious flawed results in (Liu, 2020), and we propose a diagnosis algorithm to establish the $t/k$ t / k -diagnosability for a large-scale connected network $G$ G under the PMC model by considering its $h$ h -extra connectivity. Let $\kappa _h(G)$ κ h (G) be the $h$ h -extra connectivity of $G$ G . Then, we can deduce that $G$ G is $\kappa _h(G)/h$ κ h (G) / h -diagnosable under the PMC model with some basic conditions. All $\kappa _h(G)$ κ h (G) faulty nodes can be correctly diagnosed in the large-scale connected network $G$ G and at most $h$ h fault-free nodes would be misdiagnosed as faulty. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. We will apply the newly found relationship to directly obtain the $\kappa _h(G)/h$ κ h (G) / h -diagnosability of a series of well known networks, including hypercubes, folded hypercubes, balanced hypercubes, dual-cubes, BC graphs, star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, alternating group graphs, split-star networks, $k$ k -ary $n$ n -cubes and $(n,k)$ (n , k) -star graphs. [ABSTRACT FROM AUTHOR]

For interconnection network losing processors, usually, when the surviving network has a large connected component, it can be used as a functional subsystem without leading to severe performance degradation. Consequently, it is crucial to characterize the interprocessor communication ability and efficiency of the surviving structure. In this article, we prove that when a subset $D$ of at most $6n-17$ processors is deleted from an $n$ -dimensional alternating group graph $\text{AG}_n$ , there exists a largest component with cardinality greater or equal to $|V(\text{AG}_n)|-|D|-3$ for $n\geq 6$ in the remaining network, and the union of small components is, first, an empty graph; or, second, a 3-cycle, or an edge, or a 2-path, or a singleton; or, third, an edge and a singleton, or two singletons. Then, we prove that when a subset $D$ of at most $8n-25$ processors is deleted from $\text{AG}_n$ , there exists a largest component with cardinality greater or equal to $|V(\text{AG}_n)|-|D|-5$ for $n\geq 6$ in the remaining network, and the union of small components is, first, an empty graph; or, second, a 5-cycle, or a 4-path, or a 4-claw, or a 4-cycle, or a 3-path, or a 3-claw, or a 3-cycle, or a 2-path, or an edge, or a singleton; or, third, a 4-cycle and a singleton, or a 3-path and a singleton, or a 3-claw and a singleton, or a 2-path and a singleton, two edges, an edge and a singleton, or two singletons; or, fourth, two edges and a singleton, or a 2-path and two singletons, or an edge and two singletons, or three singletons. [ABSTRACT FROM AUTHOR]

A network's diagnosability is the maximum number of faulty vertices that the network can discriminate solely by performing mutual tests among vertices. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. The h-extra fault diagnosability is an important and widely accepted diagnostic strategy as a new measure of diagnosability, which guarantees that the scale of every component is at least h+1 in the remaining system. Moreover, it increases the allowed faulty vertices, hence enhancing the diagnosability of the network. There have been lots of state-of-the-art literatures concerning the h-extra fault diagnosability. Although there are some methods to theoretically prove the extra fault diagnosability of some other well-known networks under MM* model, these methods have some serious flaws when there exists a 4-cycle in these networks. In this article, we investigate the reason that caused the flawed results in some references, and we derive a different, broadly applicable, and complete fault tolerant method to establish the extra fault diagnosability in an n-dimensional alternating group graph AGn under MM* model. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. Moreover, we compare the extra fault diagnosability of AGn with various types of fault diagnosability, including the diagnosability, strong diagnosability, conditional diagnosability, t/k-diagnosability, and pessimistic diagnosability. It can be seen that the extra fault diagnosability is greater than all the other types of fault diagnosability. [ABSTRACT FROM AUTHOR]

The extra connectivity and extra diagnosability are two important measures for network reliability. Under MM* model, two possible relationships between extra connectivity and extra diagnosability were proposed in Reference [24]. However, there are some shortcomings in it: (1) the conclusion of Theorem 3.9 is wrong; (2) the corresponding proof of Theorem 3.9 is flawed; (3) the exact relationship is still not clear. In this paper, we impose reasonable constraints, and give a new and correct proof for measuring the exact relationship between h -extra connectivity κ h (G) and h -extra diagnosability t h m ˜ (G) of the regular connected graph G under MM* model, which is t h m ˜ (G) = κ h (G) + h. As an application, we directly obtain the h -extra diagnosability of star graph S n , alternating group graph network A N n and (n , k) -star graph S n , k by our proposed new result. [ABSTRACT FROM AUTHOR]

The restricted connectivity and the g -good-neighbor diagnosability are two important indicators of the robustness for a multi-processor system in presence of failing processors. The g -good-neighbor diagnosability of a graph guarantees that the number of fault-free neighbors of every fault-free vertex is greater or equal to g in the graph. We first establish the 3-restricted connectivity of an n -dimensional split-star network S n 2. Then we propose the upper bound of the { 1 , 2 , 3 } -good-neighbor diagnosability of S n 2 under the MM* model. Moreover, we show that when deleting two indistinguishable good-neighbor faulty vertex-sets from S n 2 , the remaining connected subgraph has no isolated vertex. Furthermore, we give a complete proof for the lower bound of the { 1 , 2 , 3 } -good-neighbor diagnosability of S n 2 , and prove that the lower and upper bounds of the { 1 , 2 , 3 } -good-neighbor diagnosability of S n 2 are accurate. [ABSTRACT FROM AUTHOR]

The significant increase in the number of processors of multiprocessor system increases its vulnerability to component failures. Diagnosability is an important indicator for the reliability of interconnection networks. The g-good-neighbour 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 neighbours (i.e. good neighbours). In this paper, we establish that the 1-good-neighbour conditional diagnosability of (n , k) -enhanced hypercube network Q n , k under PMC model is 2n−1 for n = k + 1 and k ≥ 3 , or 2n + 1 for n>k + 1 and k ≥ 3 , respectively. Moreover, the 2-good-neighbour conditional diagnosability of Q n , k is 3n−3 for n = k + 1 and k ≥ 4 , or 4n−5 for n = k + 2 and k ≥ 3 , or 4n−1 for n>k + 2 and k ≥ 3 , respectively. [ABSTRACT FROM AUTHOR]

Connectivity plays an crucial role in measuring the fault tolerance of a multiprocessor system in the case of vertices failures. Extra connectivity is an important indicator of a network's ability for diagnosis and fault tolerance. In this paper, we analyse the fault tolerance ability of the n , k -dimensional enhanced hypercube, a well-known interconnection network denoted by Q n , k proposed for multiprocessor systems, and establish the { 1 , 2 , 3 } -extra connectivity of Q n , k . [ABSTRACT FROM AUTHOR]

The h -extra diagnosability and g -good-neighbor diagnosability are two important diagnostic strategies at system-level that can significantly enhance the system's self-diagnosing capability. The h -extra diagnosability ensures that every component of the system after removing a set of faulty vertices has at least h + 1 vertices. The g -good-neighbor diagnosability guarantees that after removing some faulty vertices, every vertex in the remaining system has at least g neighbors. In this paper, we analyze the extra diagnosability and good-neighbor diagnosability in a well-known n -dimensional alternating group graph A G n proposed for multiprocessor systems under the PMC model. We first establish that the 1-extra diagnosability of A G n (n ≥ 5) is 4 n − 10. Then we prove that the 2-extra diagnosability of A G n (n ≥ 5) is 6 n − 17. Next, we address that the 3-extra diagnosability of A G n (n ≥ 5) is 8 n − 25. Finally, we obtain that the g -restricted connectivity and the g -good-neighbor diagnosability of A G n (n ≥ 5) are (2 g + 2) n − 2 g + 2 − 4 + g and (2 g + 2) n − 2 g + 2 − 4 + 2 g for 1 ≤ g ≤ 2 , respectively. [ABSTRACT FROM AUTHOR]

The probability of having faults in a multiprocessor computer system increases as the size of system grows. One way to quantify the reliability of a system is using the probability that a fault-free subsystem of a certain size still exists with the presence of individual faults. The higher the probability is, the more reliable the system is. In this paper, we establish the reliability for networks based on A G n , the n -dimensional alternating group graph. More specifically, we calculate the probability of a subnetwork (or subgraph) A G n n − 1 being fault-free, when given a single node's fault probability. Since subnetworks of A G n intersect in highly complex manners, our scheme is to use the Principle of Inclusion–Exclusion to obtain a lower-bound of the probability, by considering intersections of up to four subgraphs. We show that the lower-bound derived this way is very close to the upper-bound obtained in a previous result, which means the lower-bound we get is a very tight one. Therefore, both lower-bound and upper-bound are close approximations of the accurate probability. [ABSTRACT FROM AUTHOR]

A t / s -diagnosable system refers to such a system that all the faulty nodes of the system can be isolated within a set of size at most s in the presence of at most t faulty nodes. Moreover, it increases the allowed faulty nodes, hence enhancing the diagnosability of the system. We can find that the t / s -diagnosability of n -dimensional folded hypercube F Q n has not been studied under the PMC model and MM* model. In this paper, we determine the t / s -diagnosability of F Q n under the PMC model and MM* model. First, we propose some new fault tolerant properties of F Q n. Then we prove that the t / s -diagnosability of n -dimensional folded hypercube F Q n is (n + 1) g − 1 2 (g − 1) (g + 2) for 2 ≤ g ≤ 1 2 (n − 1) where s = (n + 1) g − 1 2 (g − 1) (g + 2) + g − 2 under both the PMC model and MM* model. In addition, we establish two t / s -diagnosis algorithms of complexity O (N l o g 2 N) and complexity O (N (l o g 2 N) 2) to isolate the faulty nodes in a node subset of the system under the PMC model and MM* model, respectively. The comparison analysis results showed that the t / s -diagnosability of F Q n is the largest, and it increases faster than the other types of diagnosability as n increases. [ABSTRACT FROM AUTHOR]

The survivable mapping problem in an IP-over-WDM network with a logical graph and physical graph is the problem of finding a mapping of a logical network in a physical layer so that any failure in physical topology does not break the logical topology's connection. Determining whether a survivable mapping against failure exists is an NP-complete problem, and therefore many heuristic algorithms have been proposed in the literature. In this paper, a heuristic mapping design strategy is proposed to enable the lightpaths to more efficiently endure a node failure. We individually consider the logical topology by building a Hamiltonian cycle and then deal with the mapping problem for disjoint physical paths. Experimental results demonstrate that the proposed algorithm can provide efficient survivable mapping in IP-over-WDM networks. The simulation shows that the survivability of previous methods (SNF and SMART-Node) is around 60–80%, but our proposed algorithm can build survivable mapping in all kinds of situations. [ABSTRACT FROM AUTHOR]

The connectivity of a graph is a classic measure for fault tolerance of the network. Restricted connectivity measure is a crucial subject for a multiprocessor system's ability to tolerate fault processors, and improves the connectivity measurement accuracy. Furthermore, if a network possesses a restricted connectivity property, it is more reliable with a lower vertex failure rate compared with other networks. The |$\left (n,k\right)$| -dimensional enhanced hypercube, denoted by |$Q_{n,k}$|⁠ , a variant of hypercube, which is a well-known interconnection network. In this paper, we analyze the fault tolerant properties for |$\left (n,k\right)$| -enhanced hypercube, and establish the |$1$| -restricted connectivity of |$Q_{n,k} (n\ge k+1)$| and |$\{2,3\}$| -restricted connectivity of |$(n,k)$| -enhanced hypercube |$Q_{n,k} (n=k+1)$|⁠. Furthermore, we propose the tight upper bound of |$\{2,3\}$| -restricted connectivity of |$Q_{n,k} (n> k+1)$|⁠. Moreover, we show many figures to better illustrate the process of the proofs. [ABSTRACT FROM AUTHOR]

A network's diagnosability is the maximum number of faulty vertices that the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The g -good-neighbor conditional diagnosability is the maximum cardinality of g -good-neighbor conditional fault-set that the system is guaranteed to identify. The g -good-neighbor conditional diagnosability of E H (s, t) under the PMC model has been proposed by Liu et al. [Liu, X. Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol. 35, 390–393]. However, the method by Liu et al. [Liu, X. Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol. 35, 390–393] is too complicated to follow, and it is not complete. We will propose a complete method to establish the g -good-neighbor conditional diagnosability of E H (s, t) under the PMC model by optimizing the structure of the proof in [Liu, X. Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol. 35, 390–393] and adding the missing case. Also we add a ratio in a table to represent the probability that a faulty set with size s contains all neighbors of any vertex, which is very low. Moreover, we mainly establish the g -good-neighbor conditional diagnosability for exchanged hypercube E H (s, t) under the comparison model. [ABSTRACT FROM AUTHOR]