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* mo...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2007-12, Vol.56 (12), p.1612-1618
Main Authors: Yang, Xiaofan, Yan Tang, Yuan
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Availability
Classification algorithms
comparison model
Complexity theory
Computer simulation
Consumption
Deltas
diagnosable system
Diagnosis
diagnosis algorithm
Fault diagnosis
Fault location
Faults
Multicomputer
PMC model
Program processors
system-level diagnosis
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 times Delta 3 times 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 Lt n.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2007.70769