Bibliographic Details
| Title: |
A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology. |
| Authors: |
Ziwich, Roverli P.1, Duarte, Elias P.1 |
| Source: |
IEEE Transactions on Parallel & Distributed Systems. Nov2016, Vol. 27 Issue 11, p3131-3143. 13p. |
| Subjects: |
Computer diagnostic software, Parallel processing, Distributed computing, Fault-tolerant computing, Computer reliability, Computer systems, Multiprocessors |
| Abstract: |
Comparison-based diagnosis is a practical approach to detect faults in hardware, software, and parallel and distributed systems. Diagnosis is based on the comparison of task outputs returned by pairs of system units. This work introduces a novel diagnosis algorithm to identify faults in $t$ -diagnosable systems of arbitrary topology under the MM* model. The complexity of the proposed algorithm is $O(t^2 \Delta N)$ in the worst case for a system with $N$ units, where $t$ denotes the maximum number of faulty units allowed and $\Delta$ corresponds to the maximum degree of a unit in the system. This complexity is nearly optimal in the sense that it is very close to that of traversing the syndrome once. Besides the algorithm specification and correctness proofs, simulations results are also presented, showing the typical performance of the algorithm for different systems. [ABSTRACT FROM PUBLISHER] |
|
Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
