On the Power of Cliques in the Parameterized Verification of Ad Hoc Networks

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.