On the reliability of alternating group graph-based networks

Yanze Huang, Limei Lin, Dajin Wang

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)9-28
Number of pages20
JournalTheoretical Computer Science
Volume728
DOIs
StatePublished - 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 journalArticleResearchpeer-review

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

VL - 728

SP - 9

EP - 28

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -