%0 Journal Article
%T A generalized model for distributed comparison-based system-level diagnosis
%A Albini
%A Luiz Carlos Pessoa
%A Duarte Jr
%A Elias Proc¨®pio
%A Ziwich
%A Roverli Pereira
%J Journal of the Brazilian Computer Society
%D 2005
%I Springer
%R 10.1590/S0104-65002005000100005
%X 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 log2n testing rounds. furthermore, a formal proof of the maximum number of tests required per testing round is presented, which can be o(n3). simulation results are also presented.
%K distributed diagnosis
%K system-level diagnosis
%K comparison-based diagnosis.
%U http://www.scielo.br/scielo.php?script=sci_abstract&pid=S0104-65002005000100005&lng=en&nrm=iso&tlng=en