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

AbstractComparison-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 N stands for the total number of nodes. In comparison, the classical Sengupta–Dahbura diagnosis algorithm takes as much as 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