A Nearly Optimal Comparison-Based Diagnosis Algorithm for Systems of Arbitrary Topology

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.