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 (N log(2)(2) N) time, where N stands for the total number of nodes. In comparison, the classical Sengupta-Dahbura diagnosis algorithm takes as much as O (N-5) 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. (c) 2007 Elsevier Ltd. All rights reserved.