Journal
THEORETICAL COMPUTER SCIENCE
Volume 757, Issue -, Pages 44-55Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.07.017
Keywords
PMC model; MM* model; (n, k)-star network; g-extra connectivity; g-extra conditional diagnosability; t/m-diagnosability
Categories
Funding
- National Natural Science Foundation of China [61572010, 61602118, 61702100]
- China Postdoctoral Science Foundation [2017M612107, 2018T110636]
- Natural Science Foundation of Fujian Province [2017J01738, 2015J01240, JAT170118]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available