6 papers
Running Time Analysis of Broadcast Consensus Protocols
Philipp Czerner, Stefan Jaax
Broadcast consensus protocols (BCPs) are a model of computation, in which anonymous, identical, finite-state agents compute by sending/receiving global broadcasts. BCPs are known t…
Peregrine 2.0: Explaining Correctness of Population Protocols through Stage Graphs
Javier Esparza, Martin Helfrich, Stefan Jaax +1
We present a new version of Peregrine, the tool for the analysis and parameterized verification of population protocols introduced in [Blondin et al., CAV'2018]. Population protoco…
The Complexity of Verifying Population Protocols
Javier Esparza, Stefan Jaax, Mikhail Raskin +1
Population protocols [Angluin et al., PODC, 2004] are a model of distributed computation in which indistinguishable, finite-state agents interact in pairs to decide if their initia…
Succinct Population Protocols for Presburger Arithmetic
Michael Blondin, Javier Esparza, Blaise Genest +2
Angluin et al. proved that population protocols compute exactly the predicates definable in Presburger arithmetic (PA), the first-order theory of addition. As part of this result,…
On Affine Reachability Problems
Stefan Jaax, Stefan Kiefer
We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, h…
Expressive Power of Broadcast Consensus Protocols
Michael Blondin, Javier Esparza, Stefan Jaax
Population protocols are a formal model of computation by identical, anonymous mobile agents interacting in pairs. Their computational power is rather limited: Angluin et al. have…