Search

The fault diagnosability of a network indicates the self-diagnosis ability of the network, thus it is an important measure of robustness of the network. As a neoteric feature for measuring fault diagnosability, the r -component diagnosability ct r (G) of a network G imposes the restriction that the number of components is at least r in the remaining network of G by deleting faulty set X , which enhances the diagnosability of G . In this article, we establish the r -component diagnosability for n -dimensional hierarchical cubic network HCN n , and we show that, under both PMC model and MM* model, the r -component diagnosability of HCN n is rn -½( r -1) r +1 for n ≥ 2 and 1≤ r≤ n-1 . Moreover, we introduce the concepts of 0-PMC subgraph and 0-MM* subgraph of HCN n . Then, we make use of 0-PMC subgraph and 0-MM* subgraph of HCN n to design two algorithms under PMC model and MM* model, respectively, which are practical and efficient for component fault diagnosis of HCN n . Besides, we compare the r -component diagnosability of HCN n with the extra conditional diagnosability, diagnosability, good-neighbor diagnosability, pessimistic diagnosability, and conditional diagnosability, and we verify that the r -component diagnosability of HCN n is higher than the other types of diagnosability.

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$ .

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.

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}$.

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.

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.

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.

The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network, such as botnet attack, DDoS attack, and Local Area Network Denial attack. Current various kinds of connectivity do not well reflect the fault tolerance of a network under these attacks. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let $G$ G be a network, $C\subset V(G)$ C ⊂ V ( G ) and $G[C]$ G [ C ] be a connected subgraph . Then $C$ C is called an $h$ h -faulty-block of $G$ G if $G-C$ G - C is disconnected, and every component of $G-C$ G - C has at least $h+1$ h + 1 nodes. The minimum cardinality over all $h$ h -faulty-blocks of $G$ G is called $h$ h -faulty-block connectivity of $G$ G , denoted by ${FB}\kappa _h(G)$ F B κ h ( G ) . In this article, we determine ${FB}\kappa _h(Q_n)$ F B κ h ( Q n ) for $n$ n -dimensional hypercube $Q_n$ Q n ( $n\geq 4$ n ≥ 4 ), a classic interconnection network. We establish that ${FB}\kappa _h(Q_n)=(h+2)n-3h-1$ F B κ h ( Q n ) = ( h + 2 ) n - 3 h - 1 for $0\leq h\leq 1$ 0 ≤ h ≤ 1 , and ${FB}\kappa _h(Q_n)=(h+2)n-4h+1$ F B κ h ( Q n ) = ( h + 2 ) n - 4 h + 1 for $2\leq h\leq n-2$ 2 ≤ h ≤ n - 2 , respectively. Larger $h$ h -faulty-block connectivity implies that an attacker will have to stage an attack to a bigger block of connected nodes, so that each remaining components will not be too small, which will in turn limit the size of large components. In other words, there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. The larger the $h$ h -faulty-block, the more difficult for an attacker to achieve that goal. As a consequence, the resistance of the network against the attacker will increase. Our experiments also show that as $h$ h increases, the $h$ h -faulty-block gets larger, and the size disparity between any two remaining components decreases. In turn, as expected, the size of the largest remaining communication group becomes smaller.

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 $AG_n$ 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 $AG_n$ 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.

A novel catalytic asymmetric reaction is reported where the regiodivergent desymmetrisation of meso-azabicycloheptene via allylic oxidation using a single chiral copper catalyst produced two different, enantioenriched structural isomers in high optical purity starting from a single compound. The enantioselectivity of the two structurally isomeric compounds was enriched to >99.5% ee after derivatization.

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.

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.

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.

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.

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.

A mobile social network (MSN) consists of certain amount of mobile users with social characteristics, and it provides data delivery concerning social relationships between mobile users. In MSN, ordinary people contact each other more frequently if they have more social features in common. In this paper, we apply a new topology structure–priority relation graph (PRG) to evaluate the data delivery routing in MSN on the system-level. By using the natural order of nodes’ representation, the diameter, the regular degree and the multi-path technology, we determine the priority relation graph-based social feature routing (PRG-SFR) algorithm to find disjointed multi-paths in MSN. Here, the multi-path technology can be exploited for ensuring that, between each pair of sender and receiver, the important information can be delivered through a highly reliable path. Then we calculate the tolerant ability of ‘faults’ and estimate the availability of MSN on the theoretical level. Finally, we analyze the efficiency of PRG-SFR algorithm from the numerical standpoint in terms of fault tolerance, forwarding number, transmission time and delivery rate. Moreover, we make comparisons between PRG-SFR algorithm and certain state-of-the-art technologies.

The minimum neighborhood and combinatorial property are two important indicators of fault tolerance of a multiprocessor system. Given a graph $G$ , $\theta _{G}(q)$ is the minimum number of vertices adjacent to a set of $q$ vertices of $G$ ( $1\leq q\leq |V(G)|$ ). It is meant to determine $\theta _{G}(q)$ , the minimum neighborhood problem (MNP). In this paper, we obtain $\theta _{AG_{n}}(q)$ for an independent set with size $q$ in an $n$ -dimensional alternating group graph $AG_{n}$ , a well-known interconnection network for multiprocessor systems. We first propose some combinatorial properties of $AG_{n}$ . Then, we study the MNP for an independent set of two vertices and obtain that $\theta _{AG_{n}}(2)=4n-10$ . Next, we prove that $\theta _{AG_{n}}(3)=6n-16$ . Finally, we propose that $\theta _{AG_{n}}(4)=8n-24$ .

The failure of some key vertices in a network, due to either attacks or malfunctioning, may break the network into several disconnected components-the vertices within each component are connected, but there are no connections between components. When this happens, two measures should be of concern: (1) the number of components in the remaining network; and (2) the size of each component. When a given number of “break vertices”are removed from a network, we hope to have as few components as possible in the remaining network. On the other hand, it is certainly desirable that the components are as large as possible. Therefore both the number of components and the size of the maximal component after removing certain vertices can be a metric of a network's fault tolerability, an important dimension of its robustness. In this paper, we examine the split-star, denoted S2n, in terms of this metric. We prove that when an arbitrary subset of vertices D with |D| ≤ 6n-15 is removed from S2n, the remaining network will have at most 3 components, with the largest component having at least n! - |D| -3 vertices. With |D| ≤ 8n -21, the remaining network has at most 4 components, with the largest component's size at least n!-|D|-5. As a theoretical application, the r-component connectivity of S2n is estimated by using the obtained maximal component and the minimal neighbor-set of independent set of size r. Moreover, we present a bound of r-component edge connectivity on S2n by considering the minimal neighbor edge-set of appropriate substructures in S2n.

A novel catalytic asymmetric reaction is reported where the regiodivergent desymmetrisation of

Privacy protection of individual users in social networks is becoming more and more important, thus it requires effective anonymization techniques. In this paper, we use Kruskal and Prim algorithms to model the linear programming of the minimum spanning tree. Finally, we execute the experiments on the number of anonymity solutions and time with different edge weights to analyze the Kruskal algorithm and Prim algorithm to verify their anonymity feasibility.

The network's diagnosability implies its self-diagnostic capability. Compared with classical sequential diagnosis that has been widely used to identify faulty nodes, the -diagnosis is considered as...

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.

Fault diagnosability is utilized as a significant measure that reflects the reliability of a multiprocessor system. However, people frequently pay close attention to the entire system’s diagnosability while ignoring the system’s important local information. The $m$ -fault-free-neighbor local fault diagnosability (for short, $m$ -FFNLFD) is a novel indicator, which describes the diagnosability of a system at a local node with $m$ fault-free neighbors. In this paper, we propose the $m$ -FFNLFD of general networks at local node under the Preparata Metze Chien model. Moreover, we also characterize some important properties of $m$ -FFNLFD of a multiprocessor system under the comparison model. Furthermore, we apply our proposed conclusions to directly obtain the $m$ -FFNLFD of 11 well-known networks under PMC-M and MM*-M, including hypercubes, locally twisted cubes, $k$ -ary $n$ -cubes, crossed cubes, twisted hypercubes, exchanged hypercubes, star graphs, $(n,k)$ -star graphs, $(n,k)$ -arrangement graphs, data center network DCells and BCDCs. Finally, we compare the $m$ -FFNLFD with both diagnosability and conditional diagnosability, and it is shown that the $m$ -FFNLFD is greater than all the other fault diagnosabilities.