Simulation of a Distributed Connectivity Algorithm for General Topology Networks - Duarte Jr., Elias Procópio; Weber, Andréa (Anais do Workshop de Testes e Tolerância a Falhas (WTF); 2002: Anais do III Workshop de Testes e Tolerância a FalhasDO - 10.5753/wtf.2002.23409, 2002)
The Distributed Network Connectivity algorithm allows every node in a general topology network to determine to which portions of the network it is connected, and which portions are unreachable. The algorithm consists of three phases: test, dissemination, and connectivity computation. During the testing phase each fault-free node tests all its neighbors at each testing interval. Upon the detection of a new fault event, the tester starts the dissemination phase, in which a reliable broadcast algorithm is employed to inform the other connected nodes about the event. At any time, any working node may run the third phase, in which a graph connectivity algorithm shows the complete network connectivity. Extensive simulation results are presented, considering various topologies such as the hypercube and random graphs. Results are compared to those of other algorithms.