On Reliability of Multiprocessor System Based on Star Graph
Mengjie Lv, Shuming Zhou, Gaolin Chen, Lanxiang Chen, Jiafei Liu, Chin‐Chen Chang · IEEE Transactions on Reliability · 2019
As a critical parameter in evaluating the reliability of a multiprocessor system when processors malfunction, the \boldmath h-extra connectivity (h-EC) of a multiprocessor system modeled by a graph G, denoted by κo(h)(G), is an h-extra vertex-cut with minimum cardinality. Both of the h-extra conditional diagnosability (h-ECD) and the t/h-diagnosability of the multiprocessor system are vital to tolerate and diagnose faulty processors. These two parameters rely on the resolving of hEC. For the multiprocessor system based on star graph Sn, we show that the 5-EC κo(5)(Sn) of Sn(n ≥ 5) is 6n - 18. As a by-product, we present a novel proof of κo(2)(Sn) = 3n - 7 (resp., κo(4)(Sn) = 5n - 14) by relaxing the restriction n ≥ 10 (resp., n ≥ 7) to n ≥ 5 (resp., n ≥ 5). Furthermore, we determine that the h-ECD of Sn(n ≥ 5) under the preparata, metze, and chien (PMC) model is (h + 1)n - 2h - 1 for 1 ≤ h ≤ 3 and (h + 1)n - 3h + 2 for 4 ≤ h ≤ 5. In addition, we show that Snis [(h + 1)n - 4h + 2]/h-diagnosable for 4 ≤ h ≤ 5, which extends the result that Snis [(h + 1)n - 3h - 1]/h-diagnosable for 1 ≤ h ≤ 3 by [Zhou et al. “The t/k-diagnosability of star graph networks,” IEEE Trans. Comput., vol. 64, no. 2, pp. 547-555, Feb. 2015].