An isochronous testing strategy for hierarchical adaptive distributed system-level diagnosis

Distributed System-level diagnosis allows the fault-free components of a fa ult-tolerant distributed system to determine which components of the system are faulty and which are fault-free. The time it takes for nodes running t he algorithm to diagnose a new event is called the algorithm's latency. In this paper we present a new distributed system-level diagnosis algorithm wh ich presents a latency of O(log N) testing rounds, for a system of N nodes. A previous hierarchical distributed system-level diagnosis algorithm, Hi-A DSD, presents a latency of O(log(2) N) testing rounds. Nodes are grouped in progressively larger logical clusters for the purpose of testing. The algo rithm employs an isochronous testing strategy that forces all fault-free no des to execute tests on clusters of the same size each testing round. This strategy is based on two main principles: a tested node must test its teste r in the same round; a node only accepts tests according to a lexical prior ity order. We present formal proofs that the algorithm's latency is at most 2log N - 1 testing rounds and that the testing strategy of the algorithm l eads to the execution of isochronous tests. Simulation results are shown fo r systems of up to 64 nodes.