Verification of Ad Hoc Networks with Node and Communication Failures

Abstract : We investigate the impact of node and communication failures on the decidability and complexity of parametric verification of a formal model of ad hoc networks. We start by considering three possible types of node failures: intermittence, restart, and crash. Then we move to three cases of communication failures: nondeterministic message loss, message loss due to conflicting emissions, and detectable conflicts. Interestingly, we prove that the considered decision problem (reachability of a control state) is decidable for node intermittence and message loss (either nondeterministic or due to conflicts) while it turns out to be undecidable for node restart/crash, and conflict detection.
Type de document :
Communication dans un congrès
Holger Giese; Grigore Rosu. 14th International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 32nd International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Jun 2012, Stockholm, Sweden. Springer, Lecture Notes in Computer Science, LNCS-7273, pp.235-250, 2012, Formal Techniques for Distributed Systems
Liste complète des métadonnées

https://hal.inria.fr/hal-00909367
Contributeur : Davide Sangiogi <>
Soumis le : lundi 29 mai 2017 - 16:00:51
Dernière modification le : jeudi 15 novembre 2018 - 20:26:57
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 11:32:04

Fichier

978-3-642-30793-5_15_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-00909367, version 1

Citation

Giorgio Delzanno, Arnaud Sangnier, Gianluigi Zavattaro. Verification of Ad Hoc Networks with Node and Communication Failures. Holger Giese; Grigore Rosu. 14th International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 32nd International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Jun 2012, Stockholm, Sweden. Springer, Lecture Notes in Computer Science, LNCS-7273, pp.235-250, 2012, Formal Techniques for Distributed Systems. 〈hal-00909367〉

Partager

Métriques

Consultations de la notice

431

Téléchargements de fichiers

27