期刊
THEORETICAL COMPUTER SCIENCE
卷 757, 期 -, 页码 44-55出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.07.017
关键词
PMC model; MM* model; (n, k)-star network; g-extra connectivity; g-extra conditional diagnosability; t/m-diagnosability
资金
- National Natural Science Foundation of China [61572010, 61602118, 61702100]
- China Postdoctoral Science Foundation [2017M612107, 2018T110636]
- Natural Science Foundation of Fujian Province [2017J01738, 2015J01240, JAT170118]
In the wake of rapid development of multiprocessor systems, fault tolerance of processors plays an even more vital role in measuring the reliability of a multiprocessor system. The g-extra connectivity of a multiprocessor system modeled by graph G, denoted by kappa((g) )(0)(G), is the minimum number of nodes whose deletion will disconnect the network and every remaining component has more than g vertices. The g-extra conditional diagnosability of multiprocessor system G, denoted by (t) over tilde (g)(G), is the maximum number of faulty vertices that the system can guarantee to identify under the condition that every fault-free component contains at least g +1 vertices. Only a few achievements have been established on kappa((g))(0)(G) for some special graphs with small g. In this paper, we first determine that the g-extra connectivity of (n, k)-star network S-n,S-k is K-0((g)) (S-n,S-k) = n + g (k-2) - 1 for 2 <= k <= n - 1 and 0 <= g <= n - k and then show that the g-extra conditional diagnosability of S-n,S-k under the PMC model (n >= 4,S- 2 <= k <= n - 1 and 1 <= g <= n - k) and the MM* model (n >= 6, 3 <= k <= n - 3 and 1 <= g <= min {n-k+1/4, k - 2}) is (t) over tilde (g) (S-n,S-k) = n + g(k - 1) - 1, respectively. Meanwhile, we also show that S(n,k )is (n + m (k - 2) - 1)/m-diagnosable under the pessimistic diagnostic strategy. As by-products, we derive the g-extra conditional diagnosability of n-dimensional star graph S-n (n >= 4, g = 1) and n-dimensional group network AN(n)(n >= 4, 1 <= g <= 2) under the PMC model. (C) 2018 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据