TY - JOUR

T1 - On the reliability of alternating group graph-based networks

AU - Huang, Yanze

AU - Lin, Limei

AU - Wang, Dajin

N1 - Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/6/5

Y1 - 2018/6/5

N2 - 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.

AB - 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.

KW - Intersection patterns

KW - Principle of inclusion–exclusion

KW - Probabilistic fault model

KW - Subgraph reliability

UR - http://www.scopus.com/inward/record.url?scp=85044261776&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.03.010

DO - 10.1016/j.tcs.2018.03.010

M3 - Article

AN - SCOPUS:85044261776

SN - 0304-3975

VL - 728

SP - 9

EP - 28

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -