SJStefan Jaax

Stefan Jaax

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Stefan Jaax has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Towards efficient verification of population protocols

    by Michael Blondin, Javier Esparza, Stefan Jaax, Philipp J. Meyer

    Population protocols are a well established model of computation by anonymous, identical finite-state agents. A protocol is well-specified if from every initial configuration, all fair executions of the protocol reach a common consensus. The central verification question for population protocols is the well-specification problem: deciding if a given protocol is well-specified. Esparza et al. have recently shown that this problem is decidable, but with very high complexity: it is at least as hard as the Petri net reachability problem, which is -hard, and for which only algorithms of non-primitive recursive complexity are currently known. In this paper we introduce the class $${ WS}^3$$ WS 3 of well-specified strongly-silent protocols and we prove that it is suitable for automatic verification. More precisely, we show that $${ WS}^3$$ WS 3 has the same computational power as general well-specified protocols, and captures standard protocols from the literature. Moreover, we show that the membership and correctness problems for $${ WS}^3$$ WS 3 reduce to solving boolean combinations of linear constraints over $${\mathbb {N}}$$ N . This allowed us to develop the first software able to automatically prove correctness for all of the infinitely many possible inputs.


  • Open Access

    The complexity of verifying population protocols

    by Javier Esparza, Stefan Jaax, Mikhail Raskin, Chana Weil-Kennedy

    Population protocols (Angluin et al. in PODC, 2004) are a model of distributed computation in which indistinguishable, finite-state agents interact in pairs to decide if their initial configuration, i.e., the initial number of agents in each state, satisfies a given property. In a seminal paper Angluin et al. classified population protocols according to their communication mechanism, and conducted an exhaustive study of the expressive power of each class, that is, of the properties they can decide (Angluin et al. in Distrib Comput 20(4):279–304, 2007). In this paper we study the correctness problem for population protocols, i.e., whether a given protocol decides a given property. A previous paper (Esparza et al. in Acta Inform 54(2):191–215, 2017) has shown that the problem is decidable for the main population protocol model, but at least as hard as the reachability problem for Petri nets, which has recently been proved to have non-elementary complexity. Motivated by this result, we study the computational complexity of the correctness problem for all other classes introduced by Angluin et al., some of which are less powerful than the main model. Our main results show that for the class of observation models the complexity of the problem is much lower, ranging from $$\varPi _2^p$$ Π 2 p to .


  • Open Access

    Running Time Analysis of Broadcast Consensus Protocols

    by 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 to compute all number predicates in NL = NSPACE(log n) where n is the number of agents. They can be considered an extension of the well-established model of population protocols. We investigate execution

  • Open Access

    Running Time Analysis of Broadcast Consensus Protocols

    by 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 to compute all number predicates in $$\mathsf {NL}=\mathsf {NSPACE}(\log n)$$ NL = NSPACE ( log n ) where n is the number of agents. They can be considered an extension of the well-established model of population protocols. This paper investigates execution time characteristics of BCPs. We show that every predicate computable by population protocols is computable by a BCP with expected $$\mathcal {O}(n \log n)$$ O ( n log n ) interactions, which is asymptotically optimal. We further show that every log-space, randomized Turing machine can be simulated by a BCP with $$\mathcal {O}(n \log n \cdot T)$$ O ( n log n · T ) interactions in expectation, where T is the expected runtime of the Turing machine. This allows us to characterise polynomial-time BCPs as computing exactly the number predicates in $$\mathsf {ZPL}$$ ZPL , i.e. predicates decidable by log-space, randomised Turing machine with zero-error in expected polynomial time where the input is encoded as unary.

  • Open Access

    The Complexity of Verifying Population Protocols

    by Javier Esparza, Stefan Jaax, Mikhail Raskin, Chana Weil-Kennedy

    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 initial configuration, i.e., the initial number of agents in each state, satisfies a given property. In a seminal paper Angluin et al. classified population protocols according to their communication mechanism, and conducted an exhaustive study of the expressive power of each class, that is, of the properties they can decide [Angluin et al., Distributed Computing, 2007]. In this paper we study the correctness problem for population protocols, i.e., whether a given protocol decides a given property. A previous paper [Esparza et al., Acta Informatica, 2017] has shown that the problem is decidable for the main population protocol model, but at least as hard as the reachability problem for Petri nets, which has recently been proved to have non-elementary complexity. Motivated by this result, we study the computational complexity of the correctness problem for all other classes introduced by Angluin et al., some of which are less powerful than the main model. Our main results show that for the class of observation models the complexity of the problem is much lower, ranging from ${\Pi}_2^p$ to PSPACE.

  • Peregrine 2.0: Explaining Correctness of Population Protocols Through Stage Graphs

    by Javier Esparza, Martin Helfrich, Stefan Jaax, Philipp J. Meyer


  • Open Access

    Succinct Population Protocols for Presburger Arithmetic

    by Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, Stefan Jaax

    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, they presented a procedure that translates any formula $\varphi$ of quantifier-free PA with remainder predicates (which has the same expressive power as full PA) into a population protocol with $2^{O(\text{poly}(|\varphi|))}$ states that computes $\varphi$. More precisely, the number of states of the protocol is exponential in both the bit length of the largest coefficient in the formula, and the number of nodes of its syntax tree. In this paper, we prove that every formula $\varphi$ of quantifier-free PA with remainder predicates is computable by a leaderless population protocol with $O(\text{poly}(|\varphi|))$ states. Our proof is based on several new constructions, which may be of independent interest. Given a formula $\varphi$ of quantifier-free PA with remainder predicates, a first construction produces a succinct protocol (with $O(|\varphi|^3)$ leaders) that computes $\varphi$; this completes the work initiated in [STACS'18], where we constructed such protocols for a fragment of PA. For large enough inputs, we can get rid of these leaders. If the input is not large enough, then it is small, and we design another construction producing a succinct protocol with one leader that computes $\varphi$. Our last construction gets rid of this leader for small inputs.

  • Open Access

    Towards Efficient Verification of Population Protocols

    by Michael Blondin, Javier Esparza, Stefan Jaax, Philipp J. Meyer

    Population protocols are a well established model of computation by anonymous, identical finite state agents. A protocol is well-specified if from every initial configuration, all fair executions reach a common consensus. The central verification question for population protocols is the well-specification problem: deciding if a given protocol is well-specified. Esparza et al. have recently shown that this problem is decidable, but with very high complexity: it is at least as hard as the Petri net reachability problem, which is EXPSPACE-hard, and for which only algorithms of non-primitive recursive complexity are currently known. In this paper we introduce the class WS3 of well-specified strongly-silent protocols and we prove that it is suitable for automatic verification. More precisely, we show that WS3 has the same computational power as general well-specified protocols, and captures standard protocols from the literature. Moreover, we show that the membership problem for WS3 reduces to solving boolean combinations of linear constraints over N. This allowed us to develop the first software able to automatically prove well-specification for all of the infinitely many possible inputs.

  • Open Access

    Peregrine: A Tool for the Analysis of Population Protocols

    by Michael Blondin, Javier Esparza, Stefan Jaax


  • Open Access

    Peregrine: A Tool for the Analysis of Population Protocols

    by Michael Blondin, Javier Esparza, Stefan Jaax