A Generalized Model for Distributed Comparison-Based System-Level Diagnosis

Luiz AlbiniElias Procópio Duarte Jr.Roverli Pereira Ziwich

This work introduces a new system-level diagnosismodel and an algorithm based on this model: Hi-Comp(Hierarchical Comparison-based Adaptive DistributedSystem-Level Diagnosis algorithm). This algorithm allowsthe diagnosis of systems that can be represented by a completegraph. Hi-Comp is the first diagnosis algorithm thatis, at the same time, hierarchical, distributed and comparison-based. The algorithm is not limited to crash faultdiagnosis, because its tests are based on comparisons. Toperform a test, a processor sends a task to two processorsof the system that, after executing the task, send their outputsback to the tester. The tester compares the two outputs;if the comparison produces a match, the tester considersthe tested processors fault-free; on the other hand, ifthe comparison produces a mismatch, the tester considersthat at least one of the two tested processors is faulty, butcan not determine which one. Considering a system of Nnodes, 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 requiredper testing round is presented, which can be O(N3).Simulation results are also presented.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: