As critical reliability metrics for multiprocessor systems, connectivity and diagnosability respectively determine network robustness against node failures and the capability to accurately identify faulty units. This article presents a comprehensive reliability analysis of bubble-sort networks (Bn), a class of Cayley graphs that implement adjacent-node swap operations, offering inherent advantages for distributed sorting systems. First, we investigate theh-extrar-component connectivity and diagnosability ofBnunder the Preparata-Metze-Chien (PMC) diagnostic model through rigorous topological analysis. Then, we characterize theg-good-neighborr-component connectivity and diagnosability ofBnunder the PMC model by establishing tight bounds through fault pattern analysis. In addition, we develop a three-round fault identification algorithm, TRFI-PMC, that achieves robust diagnostic performance in simulated experiments. Specifically, for the networkB8with 40320 nodes, the algorithm maintains superior performance (fault density achieving 25%) across five metrics: accuracy (98.81%), true negative rate (97.81%), false positive rate (2.18%), true positive rate (99.3%), and precision (98.98%). The theoretical results establish fundamental reliability limits forBnarchitectures, while the practical algorithm provides an efficient fault diagnosis solution forn-dimensional bubble-sort network.

With the application and rapid development of high-performance computing and cloud computing technology, the scale of the interconnection network has appeared to grow exponentially. Network attacks have become increasingly sophisticated and stealthy. To reach a high reliable network system, widespread attention has been paid to fault diagnosis. In this article, we put forward a reliable and adaptive self-diagnosis strategy, the$h$-extra$r$-component conditional diagnosability, denoted by$ct_{r}^{h}(G)$. Then, we provide a theoretical derivation to characterize the$h$-extra$r$-component conditional diagnosability of bubble sort networks$B_{n}$under the PMC model. Furthermore, we develop a fast and adaptive fault self-diagnosis algorithm FAFD-PMC to detect all faulty units. Extensive experiments are implemented and applied to synthetic networks and real networks in terms of accuracy (ACCR), true negative rate, false positive rate, recall, and precision, which demonstrates the ACCR/efficiency of our algorithm.

The underlying topology of the interconnection network of parallel and distributed systems is usually modelled by a simple connected graph$G$. In order to quantitatively analyze the reliability and fault tolerance of these networks more accurately, this study introduces a novel topology parameter. The$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(G)$of$G$, if any, is the smallest cardinality of faulty link set, whose malfunction yields a disconnected graph with at least$r+1$connected components, and with the neighboring edges of any vertex being at least$g$. When designing and maintaining parallel and distributed systems, the hypercube network$Q_{n}$is one of the most attractive interconnection network models. This article offers a unified method to derive an upper bound for$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(Q_{n})$of$Q_{n}$. When$n\geq 4$, this upper bound is proved to be tight for$1\leq 2^{g}\cdot r\leq 2^{\lfloor \frac{n}{2}\rfloor }$or$r=2^{k_{0}}$,$0\leq k_{0}< \lfloor \frac{n}{2}\rfloor$,$0\leq g\leq n-2k_{0}-1$. The conclusions for the$g$-good-neighbor edge-connectivity of$Q_{n}$from Xu and the$(r+1)$-component edge-connectivity of$Q_{n}$from Zhao et al. are contained as corollaries of our main results for$r=1$,$0\leq g\leq n-1$and$1\leq r\leq 2^{\lfloor \frac{n}{2}\rfloor }$,$g=0$, respectively.

The g-restricted connectivity (g-RC) is the minimum vertex-set size of a network, whose deletion disconnects the network such that each remaining vertex has at least g neighbors in its respective component. The g-RC is a deterministic indicator of tolerability of a network with failing processors. The g-good-neighbor fault diagnosability (g-GNFD) is the largest set size of correctly identified faulty vertices in a network such that any good vertex has no fewer g good neighbors. This paper establishes the relationship between g-RC and g-GNFD of general regular networks, first under the PMC model and second under the MM* model. Moreover, this paper directly gives the g-GNFD of some well-known special networks by their g-RC and our proposed relationship.

We consider a generalization of both the classic Steiner tree problem and the terminal Steiner tree problem. Given a complete graph${ G = (V,E)}$with a metric cost function${ c:E \rightarrow {\BBQ_ \geq }}$and two proper subsets$ R \subset V$and$ R^\prime \subseteq R$, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in$\it R$such that all vertices in$R^\prime$must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in$G$. The previously best-known approximation ratio of the problem is$ 2\rho$, where$\bf \rho$is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from$ 2\rho$to$ 2\rho - {\rho \over {3\rho - 2}} - f$, where$f$is a non-negative function whose value is between 0 and$ \rho - {\rho \over {3\rho - 2}}$.

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. This article adopts the MM* model and outlines the common properties of a wide class of interconnection networks, called component-composition graphs (CCGs), to determine their diagnosability by using their obtained properties. By applying the results to multiprocessor systems, the diagnosability of hypercube-like networks (including hypercubes, crossed cubes, Möbius cubes, twisted cubes, locally twisted cubes, generalized twisted cubes, and recursive circulants), star graphs, pancake graphs, bubble-sort graphs, and burnt pancake graphs, all of which belong to the class of CCGs, can also be computed.

A graph$G$is$k$-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most$k$vertices and/or edges from$G$, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let$\delta_{i}$be the minimum degree of$G_{i}$for$i=0$, 1. Given$(\delta_{i}-2)$-fault Hamiltonian and$(\delta_{i}-3)$-fault Hamiltonian-connected graph$G_{i}$for$i=0, 1$, this study shows that the Cartesian product network$G_{0} \times G_{1}$is$(\delta_{0}+\delta_{1}-2)$-fault Hamiltonian and$(\delta_{0}+\delta_{1}-3)$-fault Hamiltonian-connected. We then apply the result to determine the fault-tolerant Hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. This study also demonstrates that these results are worst-case optimal with respect to the number of faults tolerated.

A graph G is conditional k-edge-fault Hamiltonian if it remains Hamiltonian after deleting at most k edges and each vertex incident to at least two nonfaulty edges. A graph G is k-edge-fault Hamiltonian-connected if it remains Hamiltonian-connected after deleting at most k edges. This study shows that the conditional edge-fault Hamiltonicity of the Cartesian product network G x H can be efficiently evaluated given two graphs G and H that are edge-fault Hamilton-connected and conditional edge-fault Hamiltonian. This study uses the result to evaluate the conditional edge-fault Hamiltonicity of two multiprocessor systems, the generalized hypercubes and the nearest neighbor mesh hypercubes, both of which belong to Cartesian product networks.

A graph G = (V, E) is said to be conditional k-edge-fault pancyclic if, after removing k faulty edges from G and provided that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to \V\ inclusive. In this paper, we sketch the common properties of a class of networks called Matching Composition Networks (MCNs), such that the conditional edge-fault pancyclicity of MCNs can be determined from the derived properties. We then apply our technical theorem to show that an m-dimensional hyper-Petersen network is conditional (2m 5)-edge-fault pancyclic.

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. In this paper, we study the diagnosability of a class of networks, called Two-Matching Composition Networks (2-MCNs), each of which is constructed by connecting two graphs via two perfect matchings. By applying our result to multiprocessor systems, we also compute the diagnosability of folded hypercubes and augmented cubes, both of which belong to two-matching composition networks.

The classic problem of determining the diagnosability of a given network has been studied extensively. Under the PMC model, this paper addresses the problem of determining the diagnosability of a class of networks called (1,2)-Matching Composition Networks, each of which is constructed by connecting two graphs via one or two perfect matchings. By applying our results to multiprocessor systems, we can determine the diagnosability of hypercubes, twisted cubes, locally twisted cubes, generalized twisted cubes, recursive circulants G(2^{n},4) for odd n, folded hypercubes, augmented cubes, crossed cubes, Möbius cubes, and hyper-Petersen networks, all of which belong to the class of (1,2)-matching composition networks.

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to $|V(G)|$. In this paper, we consider the common properties of a wide class of interconnection networks, called restricted hypercube-like networks, from which their conditional edge-fault pancyclicity can be determined. We then apply our technical theorems to show that several multiprocessor systems, including n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, recursive circulants $G(2^{n},4)$ for odd n, n-dimensional crossed cubes, and n-dimensional twisted cubes for odd n, are all conditional $(2n-5)$-edge-fault pancyclic.

A graph G is called Hamiltonian if there is a Hamiltonian cycle in G. The conditional edge-fault Hamiltonicity of a Hamiltonian graph G is the largest k such that after removing k faulty edges from G, provided that each node is incident to at least two fault-free edges, the resulting graph contains a Hamiltonian cycle. In this paper, we sketch common properties of a class of networks, called matching composition networks (MCNs), such that the conditional edge-fault hamiltonicity of MCNs can be determined from the found properties. We then apply our technical theorems to determine conditional edge-fault hamiltonicities of several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and n-dimensional hyper Petersen networks. Moreover, we also demonstrate that our technical theorems can be applied to network construction.

The locally twisted cube is a variation of hypercube, which possesses some properties superior to the hypercube. In this paper, we investigate the edge-fault-tolerant Hamiltoncity of an n-dimensional locally twisted cube, denoted by LTQn. We show that for any LTQn(n ges 3) with at most 2n - 5 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. We also demonstrate that our result is optimal with respect to the number of faulty edges tolerated.

This paper proposes an agent-based computational model of a lottery market based on an expected-utility paradigm, in which agents' decisions regarding lottery participation are based on their own subjective beliefs, and those beliefs are evolving over time with genetic algorithms. The simulation results are then compared with another agent-based lottery market with different agent engineering. It is found that almost all emergent properties, such as the Laffer curve, the halo effect (lottomania), conscious-selection behavior, and the interdependent preference (regretting effect) are qualitatively robust with these two different designs of agents