Home | Search | Help  
Home Page Università di Genova

Technical Report Details

Date 12-1-2011
Number DISI-TR-11-01
Title On The Power of Cliques in the Parameterized Verification of Ad Hoc Networks
Authors Giorgio Delzanno, Arnaud Sangnier, Gianluigi Zavattaro
Bibtex Entry
E-mail giorgio@disi.unige.it
Link http://www.disi.unige.it/person/DelzannoG/papers/dsz11.pdf
Abstract We study decision problems for parameterized verification of protocols for ad hoc networks. The problem we consider is control state reachability for networks of arbitrary size. We restrict our analysis to topologies that approximate the notion of cluster (graphs with bounded diameter) often used in ad hoc networks for optimizing broadcast communication. In particular we are interested in classes of graphs that include at least cliques of arbitrary order. We show that, although decidable, control state reachability over cliques is already Ackermann-hard and study more sophisticated topologies for which the problem remains decidable.
Back to Technical Reports