The complexity of system-level fault diagnosis and diagnosability
Gregory F. Sullivan · 1986
It is now possible to design and build systems which incorporate a large number of processing elements. For this reason, fault-diagnosis at the system level, a research area pioneered by the work of Preparata, Metze, and Chien, is of increasing importance. The formalization of their model utilizes directed graphs together with labelings on edges and vertices. The two central problems introduced by the model are called the diagnosis and diagnosability problems. In the diagnosis problem an algorithm must identify the faulty units of a system based on test results. In the diagnosability problem an algorithm must determine the maximum number of faulty units a system can contain and still be guaranteed capable of successfully testing itself. We resolve one of the main open questions for this model by presenting the first polynomial time algorithm for the diagnosability problem. The solution uses network flow techniques and runs in $O(\vert E\vert\vert V\vert\sp{3/2})$ time. We also present a new time complexity bound of $O(min(t\vert E\vert,t\sp3 +\vert E\vert))$ for the diagnosis problem, where t is the maximum number of faulty units. In addition, we examine the major generalizations of the Preparata, Metze and Chien model. Maheshwari and Hakimi introduced probabilistic and weighted models. Friedman introduced a model with a measure called t/s -diagnosability. We present several new polynomial time algorithms, NP-hardness results and an approximation algorithm for these models.