Local Diagnosis Algorithms for Multiprocessor Systems Under the Comparison Diagnosis Model

Abstract—An efficient diagnosis is very important for a multi-processor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the compar-isonmodel, the diagnosis is performed by sending two identical sig-nals from a processor to a pair of distinct neighbors, and then com-paring their responses. Sengupta and Dahbura proposed a polyno-mial-time algorithm with time complexity to diagnose a system with a total number of processors under the comparison model. Recently, some concepts, such as the conditional diagnos-ability and the local diagnosability, are concernedwith themeasure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each pro-cessor for conditional local diagnosis under the comparison model. According to our results, a specific-connected network with the balanced wind-bell-tree structure is conditionally-diag-nosable, and the time complexity to diagnose all the faulty proces-sors is with our algorithm, where is the total number of the processors in the network. Index Terms—Comparison diagnosis model, conditional diag-nosability, local diagnosis, system diagnosis