Faster adaptive parallel diagnosis in the presence of intermittent faults (extended abstract)

For any multiprocessor system with n processors, which has less than n/2 faulty processors, including at most s intermittent ones, Fu and Beigel proposed an adaptive parallel fault diagnosis algorithm in O(s⁵) testing rounds. In this paper, we present an improved parallel diagnosis algorithm for the system in O(s³) testing rounds. Moreover, it is proved that any parallel diagnosis algorithm require Ω(s) testing rounds in order to diagnose the system.