The reliability of subgraphs in the arrangement graph

Limei Lin, Li Xu, Shuming Zhou, Dajin Wang

Research output: Contribution to journalArticle

17 Citations (Scopus)

Abstract

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
Volume64
Issue number2
DOIs
StatePublished - 1 Jun 2015

Fingerprint

Computer systems
Health

Keywords

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

Cite this

Lin, Limei ; Xu, Li ; Zhou, Shuming ; Wang, Dajin. / The reliability of subgraphs in the arrangement graph. In: IEEE Transactions on Reliability. 2015 ; Vol. 64, No. 2. pp. 807-818.
@article{eb9a209ba02442b1b394c975cd09c377,
title = "The reliability of subgraphs in the arrangement graph",
abstract = "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.",
keywords = "Arrangement graph, inclusion-exclusion principle, probabilistic fault model, subgraph reliability",
author = "Limei Lin and Li Xu and Shuming Zhou and Dajin Wang",
year = "2015",
month = "6",
day = "1",
doi = "10.1109/TR.2015.2413372",
language = "English",
volume = "64",
pages = "807--818",
journal = "IEEE Transactions on Reliability",
issn = "0018-9529",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

The reliability of subgraphs in the arrangement graph. / Lin, Limei; Xu, Li; Zhou, Shuming; Wang, Dajin.

In: IEEE Transactions on Reliability, Vol. 64, No. 2, 7072564, 01.06.2015, p. 807-818.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The reliability of subgraphs in the arrangement graph

AU - Lin, Limei

AU - Xu, Li

AU - Zhou, Shuming

AU - Wang, Dajin

PY - 2015/6/1

Y1 - 2015/6/1

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

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

KW - Arrangement graph

KW - inclusion-exclusion principle

KW - probabilistic fault model

KW - subgraph reliability

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

U2 - 10.1109/TR.2015.2413372

DO - 10.1109/TR.2015.2413372

M3 - Article

AN - SCOPUS:85027939968

VL - 64

SP - 807

EP - 818

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

SN - 0018-9529

IS - 2

M1 - 7072564

ER -