4 papers · 1 filter
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…
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,…
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…