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