Parameterized verification of time-sensitive models of ad hoc network protocols

详细信息    查看全文

• 作者：Parosh Aziz Abdulla^a ; ^{parosh@it.uu.se" class="auth_mail" title="E-mail the corresponding author} ; Giorgio Delzanno^b ; ^{giorgio.delzanno@unige.it" class="auth_mail" title="E-mail the corresponding author} ; Othmane Rezine^a ; Arnaud Sangnier^c ; ^{sangnier@liafa.univ-paris-diderot.fr" class="auth_mail" title="E-mail the corresponding author} ; Riccardo Traverso^d ; ^{rtraverso@fbk.eu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Parameterized verification ; Timed automata ; Ad hoc networks ; Graphs ; Decidability ; Well structured transition systems
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：25 January 2016
• 年：2016
• 卷：612
• 期：Complete
• 页码：1-22
• 全文大小：905 K

文摘

We study decidability and undecidability results for parameterized verification of a formal model of timed Ad Hoc network protocols. The communication topology is defined by an undirected graph and the behaviour of each node is defined by a timed automaton communicating with its neighbours via broadcast messages. We consider parameterized verification problems formulated in terms of reachability. In particular we are interested in searching for an initial configuration from which an individual node can reach an error state. We study the problem for dense and discrete time and compare the results with those obtained for (fully connected) networks of timed automata.