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

Authors

  • 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

DOI:

https://doi.org/10.5752/P.2316-9451.2012V1N1P5

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

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).

Downloads

Published

2012-11-30

How to Cite

WEBER, Andréa; DUARTE JR., Elias Procóprio; FONSECA, Keiko Verônica Ono. Alternative specification and correctness proofs of the distributed network reachability algorithm DOI 10.5752/P.2316-9451.2012v1n1p5. Abakós, Belo Horizonte, v. 1, n. 1, p. 5–27, 2012. DOI: 10.5752/P.2316-9451.2012V1N1P5. Disponível em: https://periodicos.pucminas.br/abakos/article/view/P.2316-9451.2012v1n1p5. Acesso em: 10 sep. 2025.

Issue

Vol. 1 No. 1 (2012)

Section

Artigos convidados / Invited papers

License

I  (we) submit the present work, an original and unpublished manuscript, from my (our) authorship, to Abakós - Magazine of Interdisciplinary Studies on Science and Informatics, and  I (we) agree that the copyright related to this work will become property of  PUC Minas Publisher. No partial or full reproduction is allowed, by any means (printed or electronic), dissociated from Abakós. Any reproduction requires prior written authorization granted by the Editor.

I (we) declare there is no type of interest conflict among the subject theme, author(s), organization(s), institution(s) and person(s).

I (we) recognize that Abakós is licensed under CREATIVE COMMONS:

Licença Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported (CC BY-NC-ND 3.0).