Adaptive System-Level Fault Diagnosis of Bijective Connection Networks

As the multiprocessor systems are becoming large-scale, fault-diagnosis is crucial to ensure the reliability of multiprocessor systems. In order to improve the self-diagnosis capability of a multiprocessor system, a pessimistic fault diagnosis scheme such as t/s-diagnosis allows some fault-free processors to be mistakenly identified as faulty. All faulty processors in at/s-diagnosable multiprocessor system (t <= s) should be identified into a set with size up to s, when the total amount of faulty processors in the system does not exceed t. This article focuses on the t/s-diagnosis for then-dimensional bijective connection network X-n. An adaptive t/s-diagnosis algorithm APDMM*t/s of complexity O(M(log(2)M)(2))under the comparison model is proposed, where M is the total amount of nodes inX(n). Then,the correctness of algorithm APDMM*t/sis proved by the fault-tolerant properties of the network itself. Moreover, we calculate the t/s-diagnosability of X-n by theoretical method in mathematics, which is-1/2y(2)+(n-1/2)y + 1for2 <= y <= n under comparison model, where s = -1/2y(2 )+ (n-1/2)y+y(-1).Furthermore, we apply algorithm APDMM*t/son the hyper cube and the real-world network WSN-DS to verify our main results,and analyze the experimental outcomes in terms of true positiverate, false positive rate, accuracy and precision. The experimental results reveal the advantage and high performance of our algorithm APDMM*t/s. Besides, we compare the t/s-diagnosability of X-n with traditional accurate diagnosability, and it turns out that as n gets larger, the t/s-diagnosability of X-n is significantly better than traditional accurate diagnosability.