Journal
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
Volume 167, Issue -, Pages 148-156Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2022.05.001
Keywords
Connectivity; Diagnosability; Hypercube; Exchanged hypercube; PMC model
Categories
Funding
- National Natural Sci-ence Foundation of China [62172291, 61972272, U1905211]
- Jiangsu Province Department of Education Future Network Re-search Fund Project [FNSRFP-2021-YB-39]
Ask authors/readers for more resources
The paper discusses the connectivity, diagnosability, and conditional diagnosability of networks based on structure faults, determining the minimum number of faulty vertices for network failure and identifying faulty vertices without replacement. Different models and variants of hypercubes are analyzed to evaluate fault-tolerability of networks, showing significant improvements in diagnosability under certain conditions.
A faulty vertex may probably affect its neighbors and further causes them being faulty, which makes a subnetwork (structure) fail. Therefore, looking into the effect caused by some structures becoming faulty is meaningful. The connectivity and diagnosability are two important parameters to evaluate the fault-tolerability of networks. The connectivity of a network is the minimum number of vertices whose removal will disconnect the network or trivial. We call the network to be t-diagnosable if the number of faulty vertices does not exceed t and all faulty vertices can be identified without a replacement. Let Q(n) be the n-dimensional hypercube and EH(s, t) be the exchanged hypercube, which is the variant of hypercube. In this paper, we study connectivity, diagnosability, and 1-good-neighbor conditional diagnosability based on structure faults, respectively. Specifically, we first determine the connectivity (1 <= k <= n - 1 and n >= 3) and diagnosability (1 <= k <= n - 1 and n >= 4) of Q(n) - Q(k) under the PMC model. Then, we determine the connectivity (2 <= k <= min{s, t}) and diagnosability (2 <= k <= min{s, t} and min{s, t} > 3) of EH(s, t) - Qk under the PMC model. Finally, we show that the 1-good-neighbor conditional diagnosability of Q(n) - Q(k) is 2n - 3 for n > 5 and 1 <= k <= n -1 under the PMC model, which is almost twice as the traditional diagnosability for a large n. (C) 2022 Elsevier Inc. 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