On the reliability of alternating group graph-based networks

Yanze Huang, Limei Lin, Dajin Wang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


The probability of having faults in a multiprocessor computer system increases as the size of system grows. One way to quantify the reliability of a system is using the probability that a fault-free subsystem of a certain size still exists with the presence of individual faults. The higher the probability is, the more reliable the system is. In this paper, we establish the reliability for networks based on AGn, the n-dimensional alternating group graph. More specifically, we calculate the probability of a subnetwork (or subgraph) AGn n−1 being fault-free, when given a single node's fault probability. Since subnetworks of AGn intersect in highly complex manners, our scheme is to use the Principle of Inclusion–Exclusion to obtain a lower-bound of the probability, by considering intersections of up to four subgraphs. We show that the lower-bound derived this way is very close to the upper-bound obtained in a previous result, which means the lower-bound we get is a very tight one. Therefore, both lower-bound and upper-bound are close approximations of the accurate probability.

Original languageEnglish
Pages (from-to)9-28
Number of pages20
JournalTheoretical Computer Science
StatePublished - 5 Jun 2018


  • Intersection patterns
  • Principle of inclusion–exclusion
  • Probabilistic fault model
  • Subgraph reliability


Dive into the research topics of 'On the reliability of alternating group graph-based networks'. Together they form a unique fingerprint.

Cite this