Fast and succinct population protocols for Presburger arithmetic

Philipp Czerner, Roland Guttenberg, Martin Helfrich, Javier Esparza

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O(m⋅n2log⁡n) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with O(m) states that run in expected O(m7⋅n2) interactions, optimal in n, for all inputs of size Ω(m). For this, we introduce population computers, a generalization of population protocols, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.

Original languageEnglish
Article number103481
JournalJournal of Computer and System Sciences
Volume140
DOIs
StatePublished - Mar 2024

Keywords

  • Fast
  • Population computers
  • Population protocols
  • Succinct

Fingerprint

Dive into the research topics of 'Fast and succinct population protocols for Presburger arithmetic'. Together they form a unique fingerprint.

Cite this