A scalable comparison-based diagnosis algorithm for hypercube-like networks

Comparison-based diagnosis is a realistic approach to detect faults in multiprocessor systems. The Maeng, Malek (MM) model for comparison-based diagnosis defines a strategy based on sending the same input (or task) from a processor to some pair of distinct neighboring processors, and then comparing their responses. Sengupta and Dahbura proposed a further modification of the MM model, called the MM* model, in which any processor v has to test another two processors if v is adjacent to them. Sengupta and Dahbura presented a O(N⁵)-time diagnosis algorithm for general diagnosable systems under the MM* model, where N is the number of processors in the system. By exploiting the cycle decomposition property, we improve the above result by presenting a O(N(log₂N)²) -time diagnosis algorithm for a class of hypercube-like networks under the MM* model.