A generalized model for distributed comparison-based system-level diagnosis

• Published in: Journal of the Brazilian Computer Society 2004-10, Vol.10 (3), p.42-54
• Main Authors: Albini, Luiz Carlos Pessoa, Duarte, Elias Procópio, Ziwich, Roverli Pereira
• Format: Article
• Language: English
• Subjects: Algorithms; Fault diagnosis
• ISSN: 0104-6500; 1678-4804
• DOI: 10.1007/BF03192365

This work introduces a new system-level diagnosis model and an algorithm based on this model: Hi-Comp (Hierarchical Comparison-based Adaptive Distributed System-Level Diagnosis algorithm). This algorithm allows the diagnosis of systems that can be represented by a complete graph. Hi-Comp is the first diagnosis algorithm that is, at the same time, hierarchical, distributed and comparison-based. The algorithm is not limited to crash fault diagnosis, because its tests are based on comparisons. To perform a test, a processor sends a task to two processors of the system that, after executing the task, send their outputs back to the tester. The tester compares the two outputs; if the comparison produces a match, the tester considers the tested processors fault-free; on the other hand, if the comparison produces a mismatch, the tester considers that at least one of the two tested processors is faulty, but can not determine which one. Considering a system of N nodes, it is proved that the algorithm’s diagnosability is (N-1) and the latency is log 2 N testing rounds. Furthermore, a formal proof of the maximum number of tests required per testing round is presented, which can be O(N 3 ). Simulation results are also presented.