Lower bounds on the state complexity of population protocols

DOI10.1007/s00446-023-00450-4arXiv2102.11619MaRDI QIDQ6096031

Jérôme Leroux, Javier Esparza, Philipp Czerner

Publication date: 11 September 2023

Published in: Distributed Computing, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed computingstate complexitypopulation protocols

Mathematics Subject Classification ID

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

Cites Work

• Linearizing well quasi-orders and bounding the length of bad sequences
• Petri nets and large finite sets
• The covering and boundedness problems for vector addition systems
• The computational power of population protocols
• Finding cut-offs in leaderless rendez-vous protocols is easy
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Complexity Hierarchies beyond Elementary
• Time-Space Trade-offs in Population Protocols
• Minimal solutions of linear diophantine systems : bounds and algorithms
• Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election
• The Reachability Problem for Petri Nets Is Not Elementary
• Complexity of controlled bad sequences over finite sets of Nd
• Computation in networks of passively mobile finite-state sensors
• Succinct Population Protocols for Presburger Arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds on the state complexity of population protocols