15 citations · 24 across the 4 of their papers we have counts for
4 papers · 1 filter
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…