Home | Search | Help  
Home Page Università di Genova

Technical Report Details

Date 22-7-2011
Number DISI-TR-11-06
Title Verification of Ad Hoc Networks with Node and Communication Failures
Authors Giorgio Delzanno, Arnaud Sangnier, Gianluigi Zavattaro
Bibtex Entry
E-mail delzanno@disi.unige.it
Link http://www.disi.unige.it/person/DelzannoG/Papers/unrel.pdf
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 in polynomial time 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.
Back to Technical Reports