VCube: A Provably Scalable Distributed Diagnosis Algorithm

VCube is a distributed diagnosis algorithm for virtually interconnecting network nodes. VCube presents several logarithmic properties, and is a logical hypercube when all nodes are fault-free. VCube is dynamic in the sense that nodes can leave and rejoin the system as they become faulty and are repaired. The topology re-organizes itself and keeps its logarithmic properties even if an arbitrary number of nodes are faulty. Fault diagnosis is based on tests. All fault-free nodes of a system with N nodes detect an event with a latency of at most log₂² N testing rounds. In this work we specify the algorithm and show that the worst number of tests executed is Nlog₂N per log₂N rounds. Besides the correctness proofs, experimental results are also given.