Hybrid fault diagnosability with unreliable communication links

Hybrid fault diagnosability in distributed multiprocessor systems is considered for the case in which, in addition to units being faulty, communication links among units can also be faulty. A hybrid fault situation is a (bounded) combination of hard and soft failing units. A novel hybrid fault diagnosability, denoted (t/t_s -unit: σ-link)-diagnosability is introduced (a total of t or fewer units can be faulty with at most t_s of them soft-failing; σ is the number of incorrect test outcomes caused by unreliable links)., This diagnosability is compatible with the previously known t/t_s-diagnosability and can additionally tolerate up to σ incorrect test outcomes to give always-correct diagnosis for any hybrid-fault (HF)-compatible syndrome from a hybrid fault situation. It is shown that an O(|E|) algorithm, proposed originally by the authors (see ibid., vol.C-35, p.503-10, 1986) for faulty unit identification in t_s-diagnosable systems, can be used to analyze a syndrome from a (t_s-unit σ-link)-diagnosable system efficiently without any preclassification of the syndrome in terms of HF-compatibility. It is shown that this algorithm not only identifies all the faulty units associated with an HF-compatible syndrome but also produces nonempty, always-correct diagnosis for many HF-incompatible syndromes