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

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.

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.