Probabilistic Reliability via Subsystem Structures of Arrangement Graph Networks
Yanze Huang, Limei Lin, Li Xu, Sun‐Yuan Hsieh
Abstract
With the rapid growth of the number of processors in a multiprocessor system, faulty processors occur in it with a probability that rises quickly. The probability of a subsystem with an appropriate size being fault-free in a definite time interval is a significant and practical measure of the reliability for a multiprocessor system, which characterizes the functionality of a multiprocessor system well. Motivated by the study of subgraph reliability, as well as the attractive structure and fault tolerance properties of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(n, k)$</tex-math></inline-formula> -arrangement graph <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$A_{n, k}$</tex-math></inline-formula> , we focus on the subgraph reliability for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$A_{n, k}$</tex-math></inline-formula> under the probabilistic fault model in this article. First, we investigate intersections of no more than four subgraphs in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$A_{n, k}$</tex-math></inline-formula> , and classify all the intersecting modes. Second, we focus on the probability <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P(q, A_{n, k}^{n-1, k-1})$</tex-math></inline-formula> with which at least one <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(n-1, k-1)$</tex-math></inline-formula> -subarrangement graph is fault-free in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$A_{n, k}$</tex-math></inline-formula> , when given a uniform probability <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$q$</tex-math></inline-formula> with which a single vertex is fault-free, and we establish the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P(q, A_{n, k}^{n-1, k-1})$</tex-math></inline-formula> by adopting the principle of inclusion–exclusion under the probabilistic fault model. Finally, we study the probabilistic fault model involving a nonuniform probability with which a single vertex is fault-free, and we prove that the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$P(q, A_{n, k}^{n-1, k-1})$</tex-math></inline-formula> under both models is very close to the asymptotic value by both theoretical arguments and experimental results.