# On the reliability of alternating group graph-based networks

Yanze Huang, Limei Lin, Dajin Wang

Research output: Contribution to journalArticle

1 Citation (Scopus)

### Abstract

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 language English 9-28 20 Theoretical Computer Science 728 https://doi.org/10.1016/j.tcs.2018.03.010 Published - 5 Jun 2018

### Fingerprint

Alternating group
Fault
Graph in graph theory
Lower bound
Subgraph
Upper bound
Multiprocessor
Intersect
n-dimensional
Subsystem
Quantify
Computer systems
Intersection
Calculate
Approximation
Vertex of a graph

### Keywords

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

### Cite this

@article{4e1634dacd1543e09630979e8a195ccc,
title = "On the reliability of alternating group graph-based networks",
abstract = "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.",
keywords = "Intersection patterns, Principle of inclusion–exclusion, Probabilistic fault model, Subgraph reliability",
author = "Yanze Huang and Limei Lin and Dajin Wang",
year = "2018",
month = "6",
day = "5",
doi = "10.1016/j.tcs.2018.03.010",
language = "English",
volume = "728",
pages = "9--28",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

On the reliability of alternating group graph-based networks. / Huang, Yanze; Lin, Limei; Wang, Dajin.

In: Theoretical Computer Science, Vol. 728, 05.06.2018, p. 9-28.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Huang, Yanze

AU - Lin, Limei

AU - Wang, Dajin

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

VL - 728

SP - 9

EP - 28

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -