Monadic Presburger Predicates have Robust Population Protocols
Monadic Presburger predicates now provably crash-proof with double-exponential state cost
Population protocols are a model of distributed computation where indistinguishable finite-state agents randomly pair up to reach consensus on whether a property holds. These protocols can decide exactly the predicates expressible in Presburger arithmetic. Recently, Lossin et al. introduced robustness against adversarial crash failures (agents can fail silently) and showed that atomic Presburger predicates are robust.
Now Czerner and colleagues prove that all monadic Presburger predicates—a much larger subclass—also have robust protocols. They also analyze state complexity: the smallest robust protocol for a given predicate requires at least double-exponential more states than the non-robust version, and they prove that Lossin et al.'s robust threshold protocols (e.g., x ≥ k) are optimal in state count. This work significantly advances the theory of fault-tolerant distributed computing by expanding the set of verifiable properties that can survive crashes.
- Proves all monadic Presburger predicates (logical statements with one quantifier) have robust population protocols that tolerate adversarial crashes
- Cost of robustness is at least double-exponential in predicate size—a steep but necessary price
- Robust threshold predicates (e.g., x ≥ k) from Lossin et al. are shown to have optimal state complexity
Why It Matters
Advances fundamental distributed computing theory; threshold predicates now have provably optimal crash-robust protocols.