The reliability of subgraphs in the arrangement graph

Limei Lin, Li Xu, Shuming Zhou, Dajin Wang

Research output: Contribution to journalArticlepeer-review

36 Scopus citations


As the size of a multiprocessor computer system grows, the probability of having faulty (i.e., malfunctioning or failing) processors in the system increases. It is then important to quantify how the faults collectively affect the entire system. The reliability of subsystems in a system, defined as the probability that a fault-free subsystem of a certain size still exists when the system has faults, is a measure for the faults' effect on the whole system. It can be used as an indicator of system health. In this paper, we will present two schemes to calculate the reliability of an $(n-1,k-1)$-subgraph in the $(n,k)$-Arrangement Graph $An,k , an extensively studied interconnection network proposed for multiprocessor computers. The first scheme will use a probability fault model and the Principle of Inclusion-Exclusion to establish an upper-bound of the reliability, by taking into account the intersection of not more than three subgraphs. The second scheme uses basically the same idea, but completely neglects the intersection among subgraphs to calculate an approximate reliability. The results of the two schemes are compared, and are shown to be in good agreement, especially as the single-node reliability $p$ goes low.

Original languageEnglish
Article number7072564
Pages (from-to)807-818
Number of pages12
JournalIEEE Transactions on Reliability
Issue number2
StatePublished - 1 Jun 2015


  • Arrangement graph
  • inclusion-exclusion principle
  • probabilistic fault model
  • subgraph reliability


Dive into the research topics of 'The reliability of subgraphs in the arrangement graph'. Together they form a unique fingerprint.

Cite this