Decidability in parameterized verification

R Bloem, S Jacobs, A Khalimov, I Konnov, S Rubin… - ACM SIGACT …, 2016 - dl.acm.org
Parameterized model checking is an active research field that considers automated
verification of distributed or concurrent systems, for all numbers of participating processes. In …

[HTML][HTML] Parameterised verification for multi-agent systems

P Kouvaros, A Lomuscio - Artificial Intelligence, 2016 - Elsevier
We study the problem of verifying role-based multi-agent systems, where the number of
components cannot be determined at design time. We give a semantics that captures …

On the complexity of parameterized reachability in reconfigurable broadcast networks

We investigate the impact of dynamic topology reconfiguration on the complexity of
verification problems for models of protocols with broadcast communication. We first …

Parameterized model checking of token-passing systems

B Aminof, S Jacobs, A Khalimov, S Rubin - International Conference on …, 2014 - Springer
We revisit the parameterized model checking problem for token-passing systems and
specifications in indexed CTL∗\X. Emerson and Namjoshi (1995, 2003) have shown that …

Model checking parameterized systems

PA Abdulla, AP Sistla, M Talupur - Handbook of model checking, 2018 - Springer
We consider the model-checking problem for a particular class of parameterized systems:
systems that consist of arbitrary numbers of components. The task is to show correctness …

On the power of cliques in the parameterized verification of ad hoc networks

G Delzanno, A Sangnier, G Zavattaro - … , FOSSACS 2011, Held as Part of …, 2011 - Springer
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 …

Parameterized verification under TSO is PSPACE-complete

PA Abdulla, MF Atig, R Rezvan - Proceedings of the ACM on …, 2019 - dl.acm.org
We consider parameterized verification of concurrent programs under the Total Store Order
(TSO) semantics. A program consists of a set of processes that share a set of variables on …

Reachability in networks of register protocols under stochastic schedulers

P Bouyer, N Markey, M Randour, A Sangnier… - arxiv preprint arxiv …, 2016 - arxiv.org
We study the almost-sure reachability problem in a distributed system obtained as the
asynchronous composition of N copies (called processes) of the same automaton (called …

Parameterized verification of asynchronous shared-memory systems

J Esparza, P Ganty, R Majumdar - … 2013, Saint Petersburg, Russia, July 13 …, 2013 - Springer
We characterize the complexity of the safety verification problem for parameterized systems
consisting of a leader process and arbitrarily many anonymous and identical contributors …

Analyzing guarded protocols: Better cutoffs, more systems, more expressivity

S Jacobs, M Sakr - … , Model Checking, and Abstract Interpretation: 19th …, 2018 - Springer
We study cutoff results for parameterized verification and synthesis of guarded protocols, as
introduced by Emerson and Kahlon (2000). Guarded protocols describe systems of …