Alternative specification and correctness proofs of the distributed network reachability algorithm DOI 10.5752/P.2316-9451.2012v1n1p5 - Weber, Andréa; Duarte Jr., Elias Procóprio; Fonseca, Keiko Verônica Ono (Abakós, 2012)
The Distributed Network Reachability algorithm allows every node in a general topology network to determine which portions of the network are reachable and unreachable. The algorithm consists of three phases: test, dissemination, and reachability computation. During the testing phase each link is tested by one of the adjacent nodes at alternating testing intervals. Upon the detection of a new event, the tester starts the dissemination phase. In this work we both give an alternative specification of DNR that employs tokens at the testing phase allowing the pair of nodes connected by a link to share testing responsibilities, and give an alternative set of proofs for the algorithm.