Probabilistic Reliability via Subsystem Structures of Arrangement Graph Networks

Yanze Huang, Limei Lin, Li Xu, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review


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><tex-math notation="LaTeX">$(n, k)$</tex-math></inline-formula>-arrangement graph <inline-formula><tex-math notation="LaTeX">$A_{n, k}$</tex-math></inline-formula>, we focus on the subgraph reliability for <inline-formula><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><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><tex-math notation="LaTeX">$P(q, A_{n, k}^{n-1, k-1})$</tex-math></inline-formula> with which at least one <inline-formula><tex-math notation="LaTeX">$(n-1, k-1)$</tex-math></inline-formula>-subarrangement graph is fault-free in <inline-formula><tex-math notation="LaTeX">$A_{n, k}$</tex-math></inline-formula>, when given a uniform probability <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula> with which a single vertex is fault-free, and we establish the <inline-formula><tex-math notation="LaTeX">$P(q, A_{n, k}^{n-1, k-1})$</tex-math></inline-formula> by adopting the principle of inclusion&#x2013;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><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.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalIEEE Transactions on Reliability
Publication statusAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering


Dive into the research topics of 'Probabilistic Reliability via Subsystem Structures of Arrangement Graph Networks'. Together they form a unique fingerprint.

Cite this