### 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 $A_{n,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 language | English |
---|---|

Article number | 7072564 |

Pages (from-to) | 807-818 |

Number of pages | 12 |

Journal | IEEE Transactions on Reliability |

Volume | 64 |

Issue number | 2 |

DOIs | |

State | Published - 1 Jun 2015 |

### Fingerprint

### Keywords

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

### Cite this

*IEEE Transactions on Reliability*,

*64*(2), 807-818. [7072564]. https://doi.org/10.1109/TR.2015.2413372

}

*IEEE Transactions on Reliability*, vol. 64, no. 2, 7072564, pp. 807-818. https://doi.org/10.1109/TR.2015.2413372

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

Research output: Contribution to journal › Article › Research › peer-review

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

VL - 64

SP - 807

EP - 818

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

SN - 0018-9529

IS - 2

M1 - 7072564

ER -