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

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.