On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks
Giorgio Delzanno, Arnaud Sangnier, Riccardo Traverso, Gianluigi Zavattaro · HAL (Le Centre pour la Communication Scientifique Directe) · 2012
We investigate the impact of dynamic topology reconfiguration on the complexity of verification problems for models of protocols with broadcast communication. We first consider reachability of a configuration with a given set of control states and show that parameterized verification is decidable with polynomial time complexity. We then move to richer queries and show how the complexity changes when considering properties with negation or cardinality constraints.