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 Ackermannhard and study more sophisticated topologies for which the problem remains decidable.
In particular, the same authors considered in REF the boundeddepth subclass of Ad Hoc Networks.
On the power of cliques in the parameterized verification of Ad Hoc networks
FoSSaCS
Computer Science