A linear time pessimistic one-step diagnosis algorithm for hypercube multicomputer systems

摘要

This paper presents a system-level diagnosis algorithm for hypercube multicomputer systems based on the PMC model. The algorithm can isolate all faulty processors to a set with at most one fault-free processor. The breadth-first search (BFS) is applied in the new algorithm. Let N denote the total number of processors in a hypercube system. With the help of properties of hypercube tree defined in this paper and a new tree-decomposition technique, the algorithm runs in O(N) time if log_2N ≥ 10; whereas the best-known diagnosis algorithm runs in O(Nlog_2N) time if log_2N ≥ 19.