The complexity of verifying population protocols

DOI10.1007/s00446-021-00390-xOpenAlexW3136017913MaRDI QIDQ2025857

Javier Esparza, Stefan Jaax, Mikhail Raskin, Chana Weil-Kennedy

Publication date: 17 May 2021

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.06578

zbMATH Keywords

distributed computingreachability analysispopulation protocolsparameterized verification

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items

Population protocols with unreliable communication, Parameterized analysis of reconfigurable broadcast networks, Population protocols: beyond runtime analysis, Protocols with constant local storage and unreliable communication

Uses Software

• PAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Verification of population protocols
• Mediated population protocols
• Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks
• Passively mobile communicating machines that use restricted space
• Complexity results for 1-safe nets
• Computation with finite stochastic chemical reaction networks
• The complexity of logical theories
• The polynomial-time hierarchy
• The computational power of population protocols
• Towards efficient verification of population protocols
• Checking qualitative liveness properties of replicated systems with stochastic scheduling
• Probability 1 computation with chemical reaction networks
• Computation in networks of passively mobile finite-state sensors
• Adding Data Registers to Parameterized Networks with Broadcast
• Temporal Logic and Fair Discrete Systems
• Satisfiability Modulo Theories
• Model Checking Parameterized Systems
• Fair Termination for Parameterized Probabilistic Concurrent Systems
• Decidability of Parameterized Verification
• Time-Space Trade-offs in Population Protocols
• Liveness of Randomised Parameterised Systems under Arbitrary Schedulers
• Model Checking Population Protocols
• Vector Addition System Reversible Reachability Problem
• Verification of Immediate Observation Population Protocols
• The reachability problem for Petri nets is not elementary
• Presburger Vector Addition Systems
• Clocked Population Protocols
• Computation in networks of passively mobile finite-state sensors
• Succinct Population Protocols for Presburger Arithmetic
• Expressive Power of Broadcast Consensus Protocols