A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM∗ model

Comparison-based diagnosis is a practical approach to the system-level fault diagnosis of multiprocessors. The locally twisted cube is a newly introduced hypercube variant, which not only possesses lower diameter and better graph embedding capability as compared with a hypercube of the same size, but retains some nice properties of hypercubes. This paper addresses the fault diagnosis of locally twisted cubes under the MM∗ comparison model. By utilizing the existence of abundant cycles within a locally twisted cube, we present a new diagnosis algorithm. With elaborately organized data, this algorithm can run in O(Nlog22N) time, where NN stands for the total number of nodes. In comparison, the classical Sengupta–Dahbura diagnosis algorithm takes as much as O(N5)O(N5) time to achieve the same goal. As a consequence, the proposed algorithm is remarkably superior to the Sengupta–Dahbura algorithm in terms of the time overhead.