Fault Tolerance of Circulant-Based Recursive Networks Built on $g$-Good Neighbor Fault Pattern

It is widely known that parallel and distributed systems are crucial technologies and platforms necessary to support supercomputing and cloud computing. The network architecture forms the foundational support for the stable operation of these systems, directly influencing their reliability, scalability, and robustness. As the network scale expands, the probability of processor/server and communication link failures increases. Therefore, it is imminent to consider how to build up the fault tolerance and reliability of the network. The circulant-based recursive networks (CRNs) are a novel type of network with several desirable properties such as regularity, recursiveness, vertex (edge) transitivity and so on. CRNs contain not only interconnection networks hypercubes and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-ary <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula>-cubes, but also data center network BCube, as well as some future networks. Connectivity and diagnosability of networks have garnered significant attention, as they suffice for analyzing and measuring networks' fault tolerance. This article focuses primarily on conditional connectivity and diagnosability under the good neighbor fault pattern. In this work, we explore the conditional connectivity and diagnosability (built on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-good neighbor fault pattern) of the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula>-dimensional <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$r$</tex-math></inline-formula>-order CRN under the PMC model and MM* model, respectively. These values are nearly <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula> times greater than the traditional connectivity and diagnosability of CRNs, respectively, implying that they can further improve fault tolerance of CRNs. Furthermore, it is worth noting that the results can be effectively utilized in BCube and other future networks given that they are both subclasses of CRNs.