Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Recenzirano
  • On Reliability of Multiproc...
    Lv, Mengjie; Zhou, Shuming; Chen, Gaolin; Chen, Lanxiang; Liu, Jiafei; Chang, Chin-Chen

    IEEE transactions on reliability, 2020-June, 2020-6-00, Letnik: 69, Številka: 2
    Journal Article

    As a critical parameter in evaluating the reliability of a multiprocessor system when processors malfunction, the \boldsymbol <inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-extra connectivity (<inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-EC) of a multiprocessor system modeled by a graph <inline-formula><tex-math notation="LaTeX">G</tex-math></inline-formula>, denoted by <inline-formula><tex-math notation="LaTeX">\kappa ^{(h)}_{o}(G)</tex-math></inline-formula>, is an <inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-extra vertex-cut with minimum cardinality. Both of the <inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-extra conditional diagnosability (<inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-ECD) and the <inline-formula><tex-math notation="LaTeX">t/h</tex-math></inline-formula>-diagnosability of the multiprocessor system are vital to tolerate and diagnose faulty processors. These two parameters rely on the resolving of <inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-EC. For the multiprocessor system based on star graph <inline-formula><tex-math notation="LaTeX">S_{n}</tex-math></inline-formula>, we show that the 5-EC <inline-formula><tex-math notation="LaTeX">\kappa ^{(5)}_{o}(S_{n})</tex-math></inline-formula> of <inline-formula><tex-math notation="LaTeX">S_{n}</tex-math></inline-formula> (<inline-formula><tex-math notation="LaTeX">n\geq 5</tex-math></inline-formula>) is <inline-formula><tex-math notation="LaTeX">6n-18</tex-math></inline-formula>. As a by-product, we present a novel proof of <inline-formula><tex-math notation="LaTeX">\kappa ^{(2)}_{o}(S_{n})=3n-7</tex-math></inline-formula> (resp., <inline-formula><tex-math notation="LaTeX">\kappa ^{(4)}_{o}(S_{n})=5n-14</tex-math></inline-formula>) by relaxing the restriction <inline-formula><tex-math notation="LaTeX">n\geq 10</tex-math></inline-formula> (resp., <inline-formula><tex-math notation="LaTeX">n\geq 7</tex-math></inline-formula>) to <inline-formula><tex-math notation="LaTeX">n\geq 5</tex-math></inline-formula> (resp., <inline-formula><tex-math notation="LaTeX">n\geq 5</tex-math></inline-formula>). Furthermore, we determine that the <inline-formula><tex-math notation="LaTeX">h</tex-math></inline-formula>-ECD of <inline-formula><tex-math notation="LaTeX">S_{n}</tex-math></inline-formula> <inline-formula><tex-math notation="LaTeX">(n\geq 5)</tex-math></inline-formula> under the preparata, metze, and chien (PMC) model is <inline-formula><tex-math notation="LaTeX">(h+1)n-2h-1</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">1\leq h\leq 3</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">(h+1)n-3h+2</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">4\leq h\leq 5</tex-math></inline-formula>. In addition, we show that <inline-formula><tex-math notation="LaTeX">S_{n}</tex-math></inline-formula> is <inline-formula><tex-math notation="LaTeX">(h+1)n-4h+2/h</tex-math></inline-formula>-diagnosable for <inline-formula><tex-math notation="LaTeX">4\leq h\leq 5</tex-math></inline-formula>, which extends the result that <inline-formula><tex-math notation="LaTeX">S_{n}</tex-math></inline-formula> is <inline-formula><tex-math notation="LaTeX">(h+1)n-3h-1/h</tex-math></inline-formula>-diagnosable for <inline-formula><tex-math notation="LaTeX">1\leq h\leq 3</tex-math></inline-formula> by Zhou et al. "The t/k-diagnosability of star graph networks," IEEE Trans. Comput. , vol. 64, no. 2, pp. 547-555, Feb. 2015.