Abstract
Diagnosis by comparison is a realistic approach to detect faults of multiprocessor systems. This paper considers a pessimistic diagnostic strategy for hypercube-like multiprocessor systems under the comparison model. The pessimistic strategy is a diagnostic process whereby all faulty nodes can be correctly identified and at most one fault-free node may be misjudged as a faulty node. We propose a pessimistic diagnosis algorithm based on the largest component in the faulty system. For a system with N=2n nodes and n≥5 , when the number of faulty nodes is bounded by 2n−2 , the algorithm can correctly identify all nodes except at most one node left undiagnosed. The time complexity of the algorithm is O(Nlog2N) .
Original language | English |
---|---|
Pages (from-to) | 2884-2888 |
Number of pages | 5 |
Journal | IEEE Transactions on Computers |
Volume | 65 |
Issue number | 9 |
DOIs | |
Publication status | Published - 2016 |
Keywords
- system-level diagnosis
- Pessimistic diagnosis
- hypercube-like networks
- the comparison model