Component Reliability of a Class of Regular Networks and Its Applications
Xueli Sun, Jianxi Fan, Shuangxiang Kan, Weibei Fan, Xiaohua Jia
Abstract
With the continuous attention to the parallel computing system, the reliability of the system, which is mainly measured by two parameters, connectivity and diagnosability, needs to be constantly studied and improved. At present, the component connectivities of some networks have been extensively studied, while the component diagnosabilities of these networks have rarely involved in. In this article, some networks with common characteristics are summarized as a class of regular networks. The definition of this kind of networks is given, and its reliability based on component failures is determined. To be specific, we prove that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$c\kappa _{m+1}(G)=m(k-1)-\binom{m}{2}+1$</tex-math></inline-formula> for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1\leq m\leq k-2$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ct_{m+1}(G)=(m+1)k-\binom{m}{2}-2\ m$</tex-math></inline-formula> for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1\leq m\leq k-2$</tex-math></inline-formula> under the PMC model, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$c\kappa _{m+1}(G)$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ct_{m+1}(G)$</tex-math></inline-formula> represent the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(m+1)$</tex-math></inline-formula> -component connectivity and the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(m+1)$</tex-math></inline-formula> -component diagnosability of such networks <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> , respectively. Based on this, we design a low time complexity component diagnosis algorithm for this kind of networks. As applications, the above two component reliability parameters of many famous networks are explored. Furthermore, the proposed diagnosis algorithm is simulated on these networks, and the results show that the algorithm has high diagnosis accuracy for various networks.