DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2026.28

Monadic Presburger Predicates Have Robust Population Protocols

Authors: Philipp Czerner, Javier Esparza, Vincent Fischer, Roland Guttenberg, Julian Pins, and Simon Reilich

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

Population protocols are a model of distributed computation in which a collection of indistinguishable finite-state agents interact randomly in pairs to decide a predicate of their initial configuration. The agents decide by achieving a stable consensus on whether the predicate holds or not. It is known that population protocols can decide exactly the predicates expressible in Presburger arithmetic. Recently, Lossin et al. have introduced a notion of protocol robustness against adversarial crash failures. They show that all atomic Presburger predicates can be decided by robust protocols, and ask whether the same holds for every Presburger predicate. We make progress towards settling this question by proving that all predicates expressible in monadic Presburger arithmetic have robust protocols. In addition, we analyze the cost of robustness in terms of state complexity. We study the ratio between the number of states of the smallest robust protocol for a given predicate and the smallest protocol for it. We show that the cost of robustness is at least double exponential in the size of the predicate, and prove that the robust protocols by Lossin et al. for threshold predicates x ≥ k have optimal state complexity.

Cite as

Philipp Czerner, Javier Esparza, Vincent Fischer, Roland Guttenberg, Julian Pins, and Simon Reilich. Monadic Presburger Predicates Have Robust Population Protocols. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{czerner_et_al:LIPIcs.CONCUR.2026.28,
  author =	{Czerner, Philipp and Esparza, Javier and Fischer, Vincent and Guttenberg, Roland and Pins, Julian and Reilich, Simon},
  title =	{{Monadic Presburger Predicates Have Robust Population Protocols}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.28},
  URN =		{urn:nbn:de:0030-drops-273585},
  doi =		{10.4230/LIPIcs.CONCUR.2026.28},
  annote =	{Keywords: Population protocols, fault-tolerance, state complexity}
}

Search Results

Documents authored by Reilich, Simon

Monadic Presburger Predicates Have Robust Population Protocols

Abstract

Cite as

Thanks for your feedback!

Could not send message