The reliability analysis based on subsystems of (n,k)-star graph

Xiaowang Li, Shuming Zhou, Xiang Xu, Limei Lin, Dajin Wang

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


As the cardinality of multiprocessor systems grows, the probability of arising malfunctioning or failing processors in the system is bound to increase. It is then of both practical and theoretical importance to know the reliability of the system as a whole. One metric for a system's overall reliability is the measurement of the collective effect of its subsystems becoming faulty. However, a challenge of this approach is that the subsystems often interact with each other in a complex manner, making the analysis difficult. Wu and Latifi (Int. Sci., vol. 178, pp. 2337-2348, Oct. 2008) proposed two schemes to evaluate the system reliability of the Star graph network under a probabilistic fault model. The first scheme computes the combinatorial probability of subgraphs to obtain an upper-bound on the reliability by considering the intersection of no more than three subgraphs. The second scheme computes an approximate combinatorial probability by completely neglecting the intersection among subgraphs. Recently, Lin et al. have applied this approach to investigate the reliability of the multiprocessor system based on the arrangement graph (IEEE Trans. Rel., vol. 62, no. 2, pp. 807-818, Jun. 2015). In this paper, we extend the above approach by computing both upper- and lower-bounds and considering the difference of the two, to establish the reliability of the (n, k) -Star graph, another extensively studied interconnection network for multiprocessor systems. More specifically, we compute a lower-bound and an upper-bound on the reliability by taking into account the intersection of no more than four or three subgraphs, respectively. The empirical study shows that the upper- and lower-bounds are both very close to the approximate results. Especially, the lower the single-node reliability goes, the closer the approximate reliability is to both lower- and upper-bounds.

Original languageEnglish
Article number7505605
Pages (from-to)1700-1709
Number of pages10
JournalIEEE Transactions on Reliability
Issue number4
StatePublished - Dec 2016


  • (n,k)-Star graph
  • approximate approach
  • probabilistic fault model
  • reliability
  • reliability of subgraphs


Dive into the research topics of 'The reliability analysis based on subsystems of (n,k)-star graph'. Together they form a unique fingerprint.

Cite this