Alternative specification and correctness proofs of the distributed network reachability algorithm DOI 10.5752/P.2316-9451.2012v1n1p5

  • Andréa Weber Universidade Federal do Paraná Departamento de Informática
  • Elias Procóprio Duarte Jr. Universidade Federal do Paraná Departamento de Informática
  • Keiko Verônica Ono Fonseca Universidade Tecnológica Federal do Paraná Departamento de Engenharia Elétrica

Resumo

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.

Biografia do Autor

Andréa Weber, Universidade Federal do Paraná Departamento de Informática
Andréa Weber is with the Department of Informatics, Federal University of Parana, where she is a professor of the Graduate Program and a researcher of the Computer Networks and Distributed Systems Lab (LarSis). Her research interests include Distributed Systems and Dependability issues, System-Level Diagnosis applications and Wireless Sensor Networks.
Elias Procóprio Duarte Jr., Universidade Federal do Paraná Departamento de Informática

Elias P. Duarte Jr. is an Associate Professor at Federal University of Parana (UFPR), Curitiba, Brazil, where he is the leader of the Computer Networks and Distributed Systems Lab (LarSis). Research interests include Computer Networks and Distributed Systems, their Dependability Management, and Algorithms.
He is a  member of the Brazilian Computer Society and the IEEE.

Keiko Verônica Ono Fonseca, Universidade Tecnológica Federal do Paraná Departamento de Engenharia Elétrica
Keiko V. O. Fonseca is with the Electrical Engineering Department, Federal University of Technology (UTFPR), Parana, where she leads a research group on high-speed networks and real-time systems. Presently, she is the Head of the Computer  Engineering Undergraduate Program of the UTFPR, Curitiba.  She is a member of the Brazilian Computer Society and the Institute of Electronics, Information, and Communication Engineers (Japan).
Publicado
30-11-2012
Como Citar
Weber, A., Duarte Jr., E. P., & Fonseca, K. V. O. (2012). Alternative specification and correctness proofs of the distributed network reachability algorithm DOI 10.5752/P.2316-9451.2012v1n1p5. Abakós, 1(1), 5-27. https://doi.org/10.5752/P.2316-9451.2012V1N1P5
Seção
Artigos convidados / Invited papers