一种高效的基于局部扭曲立方体的悲观诊断算法

An Efficient Pessimistic Diagnosis Algorithm on Locally Twisted Cube

悲观诊断与精确诊断相比,可以提高系统的自诊断能力。局部扭曲立方体是超立方体的一种变体,具有可并行处理的某些性质。在PMC模型下,研究了局部扭曲立方体的诊断问题,提出了一个O(Nlog_2N)的悲观诊断算法,N是处理器总数。经典的YML算法所需时间为O(N^(2.5)),因此,该算法在时间复杂度方面是高效的。

In comparison with precise diagnosis, pessimistic diagnosis can enhance the self-diagnosing capability of a system. Locally twisted cube is one of the hypercube variants, which possesses some features desirable for parallel processing. This paper addresses the fault diagnosis of locally twisted cube under the PMC model and propose an O（N log2 N） algorithm for pessimistic diagnosis of locally twisted cube, where N is the total number of the processors. In comparison, the classical YML algorithm takes O （N^25） time to achieve the same goal. In terms of time overload, the presented algorithm is efficient.