Reliability assessment of multiprocessor system based on (n, k)-star network

Shuming Zhou, Xiaowang Li, Jinqiang Li, Dajin Wang

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


As the size and complexity of a multiprocessor system increases, reliability evaluation becomes an important issue. The performability of a multiprocessor system heavily depends on the application program and the underlying architecture. In multitasking multiprocessor system, the problem of dynamically assigning a given dimensional subsystem to a special task is considered as a reallocation in the presence of node and/or link failures. This paper takes the generalization of star graph, (n, k)-star graph, as an empirical object. In order to measure the reliability of (n, k)star graph, the analytical model introduces mean time to failure (MTTF) to show the time that the appearance of a certain number of faulty Sn−1 ,k−1 costs. The higher the MTTF, the better the robustness. So, the way to evaluate the robustness of an (n, k)-star is to count how much the MTTF is. In fact, an (n, k)-star can be partitioned along any dimension (except the first one) with corresponding identification code. So, we will explore the reliability of (n, k)-star graph when it is partitioned along any dimension (except the first one) under node and/or link fault model. Comparisons among the simulation results under two partitioning models reveal that the MTTF is higher under liberal partition model, which better reflect the steady state of an interconnection network that can persist when the network is destroyed.

Original languageEnglish
Pages (from-to)1025-1035
Number of pages11
JournalIEEE Transactions on Reliability
Issue number4
StatePublished - Dec 2017


  • (n,k)-star
  • Mean time to failure (MTTF)
  • Node (link) failure
  • Reliability
  • Robustness


Dive into the research topics of 'Reliability assessment of multiprocessor system based on (n, k)-star network'. Together they form a unique fingerprint.

Cite this