The complexity of verifying population protocols
Open Access
- 24 March 2021
- journal article
- research article
- Published by Springer Nature in Distributed Computing
- Vol. 34 (2) , 133-177
Abstract
Population protocols (Angluin et al. in PODC, 2004) are a model of distributed computation in which indistinguishable, finite-state agents interact in pairs to decide if their initial configuration, i.e., the initial number of agents in each state, satisfies a given property. In a seminal paper Angluin et al. classified population protocols according to their communication mechanism, and conducted an exhaustive study of the expressive power of each class, that is, of the properties they can decide (Angluin et al. in Distrib Comput 20(4):279–304, 2007). In this paper we study the correctness problem for population protocols, i.e., whether a given protocol decides a given property. A previous paper (Esparza et al. in Acta Inform 54(2):191–215, 2017) has shown that the problem is decidable for the main population protocol model, but at least as hard as the reachability problem for Petri nets, which has recently been proved to have non-elementary complexity. Motivated by this result, we study the computational complexity of the correctness problem for all other classes introduced by Angluin et al., some of which are less powerful than the main model. Our main results show that for the class of observation models the complexity of the problem is much lower, ranging from $$\varPi _2^p$$ to .
Keywords
All Related Versions
Funding Information
- European Research Council (787367)
This publication has 35 references indexed in Scilit:
- Vector Addition System Reversible Reachability ProblemLogical Methods in Computer Science, 2013
- Mediated population protocolsTheoretical Computer Science, 2011
- Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networksNatural Computing, 2009
- Computation with finite stochastic chemical reaction networksNatural Computing, 2008
- The computational power of population protocolsDistributed Computing, 2007
- Computation in networks of passively mobile finite-state sensorsDistributed Computing, 2006
- Decidability and complexity of Petri net problems — An introduction1998
- Complexity results for 1-safe netsTheoretical Computer Science, 1995
- The complexity of logical theoriesTheoretical Computer Science, 1980
- The polynomial-time hierarchyTheoretical Computer Science, 1976