Model Checking Parameterised Multi-token Systems via the Composition Method

Abstract

We study the model checking problem of parameterised systems with an arbitrary number of processes, on arbitrary network-graphs, communicating using multiple multi-valued tokens, and specifications from indexed-branching temporal logic. We prove a composition theorem, in the spirit of Feferman-Vaught [21] and Shelah [31], and a finiteness theorem, and use these to decide the model checking problem. Our results assume two constraints on the process templates, one of which is the standard fairness assumption introduced in the cornerstone paper of Emerson and Namjoshi [18]. We prove that lifting any of these constraints results in undecidability. The importance of our work is three-fold: (i) it demonstrates that the composition method can be fruitfully applied to model checking complex parameterised systems; (ii) it identifies the most powerful model, to date, of parameterised systems for which model checking indexed branching-time specifications is decidable; (iii) it tightly marks the borders of decidability of this model.