Efficient fault identification of diagnosable systems under the comparison model
Diagnosis by comparison is a realistic approach to the fault diagnosis of massive multicomputers. This paper addresses the fault identification of diagnosable multicomputer systems under the MM* comparison model. We find that the fault location task can be reduced to that under the classical PMC* model. On this basis, we present an O(n x Delta(3) x delta) time diagnosis algorithm for an n-node MM* diagnosable system, where Delta and delta denote the maximum and minimum degrees of a node, respectively. The proposed algorithm is much more efficient than the fastest known diagnosis algorithm (which consumes O(n(5)) time) because realistic massive multicomputers are sparsely interconnected and, hence, Delta; delta << n.
diagnosable system comparison model multicomputer diagnosis algorithm system-level diagnosis pmc model