Conditional Diagnosability of $(n,k)$ -Star Graphs Under the PMC Model
Nai-Wen Chang, Sun‐Yuan Hsieh · IEEE Transactions on Dependable and Secure Computing · 2016
Fault diagnosis has played a major role in measuring the reliability of multiprocessor systems. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel property of measuring diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of (n, k)-star graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of (n, k)-star graphs under the PMC model, and show that it is 1) ⌈2/n⌉ -1 for n ≥ 4 and k = 1, and 2) n + 3k - 6 for 2 ≤ k ≤ n-3.