TCS Journal 2021 Journal Article
The t/s-diagnosability and t/s-diagnosis algorithm of folded hypercube under the PMC/MM* model
- Yuhang Lin
- Limei Lin
- Yanze Huang
- Jiaru Wang
A t / s -diagnosable system refers to such a system that all the faulty nodes of the system can be isolated within a set of size at most s in the presence of at most t faulty nodes. Moreover, it increases the allowed faulty nodes, hence enhancing the diagnosability of the system. We can find that the t / s -diagnosability of n-dimensional folded hypercube F Q n has not been studied under the PMC model and MM* model. In this paper, we determine the t / s -diagnosability of F Q n under the PMC model and MM* model. First, we propose some new fault tolerant properties of F Q n. Then we prove that the t / s -diagnosability of n-dimensional folded hypercube F Q n is ( n + 1 ) g − 1 2 ( g − 1 ) ( g + 2 ) for 2 ≤ g ≤ 1 2 ( n − 1 ) where s = ( n + 1 ) g − 1 2 ( g − 1 ) ( g + 2 ) + g − 2 under both the PMC model and MM* model. In addition, we establish two t / s -diagnosis algorithms of complexity O ( N l o g 2 N ) and complexity O ( N ( l o g 2 N ) 2 ) to isolate the faulty nodes in a node subset of the system under the PMC model and MM* model, respectively. The comparison analysis results showed that the t / s -diagnosability of F Q n is the largest, and it increases faster than the other types of diagnosability as n increases.