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 · 28 citations · 45 references

Concepts

Abstract

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 κ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(h)</sup> (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 κ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(5)</sup> (S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> ) of S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> (n ≥ 5) is 6n - 18. As a by-product, we present a novel proof of κ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2)</sup> (S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> ) = 3n - 7 (resp., κ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(4)</sup> (S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> ) = 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 S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> (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 S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> is [(h + 1)n - 4h + 2]/h-diagnosable for 4 ≤ h ≤ 5, which extends the result that S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> is [(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].

References

45