Conditional Diagnosability of Alternating Group Networks Under the PMC Model
Nai-Wen Chang, Sun‐Yuan Hsieh
Abstract
Fault diagnosis of processors has played an essential role when evaluating the reliability of multiprocessor systems. In many novel multiprocessor systems, their diagnosability has been extensively explored. Conditional diagnosability is a useful measure for evaluating diagnosability by adding a further condition that all neighbors of every node in the system do not fail at the same time. In this paper, we study the conditional diagnosability of n-dimensional alternating group networks ANn under the PMC model, and obtain the results tc(AN <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sub> ) = 5, and tc(ANn) = 6n - 17 for n > 5. In addition, for the isomorphism property between AN <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> and S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n,k</sub> with k = n-2, namely (n, n - 2)-star graphs S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n,n-2</sub> , the above results can be extended to S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n,n-2</sub> , and we have tc(S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4,2</sub> ) = 5 and tc(S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n,n-2</sub> ) = 6n - 17 for n > 5. It is worth noting that the conditional diagnosability is about six times the degree of ANn andS <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n,n-2</sub> , which is very different from general networks with a multiple of four.