@inproceedings{10.1145/3519270.3538421,
    Abstract = {Population protocols are a model of computation in which an arbitrary number of anonymous finite-memory agents are interacting in order to decide by stable consensus a predicate. In this paper, we focus on the counting predicates that asks, given an initial configuration, whether the number of agents in some initial state i is at least n. In 2018, Blondin, Esparza, and Jaax shown that with a fix number of leaders, there exists infinitely many n for which the counting predicate is stably computable by a protocol with at most O(log log(n)) states. We provide in this paper a matching lower-bound (up to a square root) that improves the inverse-Ackermannian lower-bound presented at PODC in 2021.},
    Address = {New York, NY, USA},
    Author = {Leroux, J\'{e}r\^{o}me},
    BookTitle = {Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing},
    File = {State Complexity of Protocols With Leaders - 3519270.3538421.pdf},
    ISBN = {9781450392624},
    Keywords = {petri nets, counting predicates, state complexity, population protocols},
    Location = {Salerno, Italy},
    Pages = {257--264},
    Publisher = {Association for Computing Machinery},
    Series = {PODC'22},
    Title = {State Complexity of Protocols with Leaders},
    URL = {https://doi.org/10.1145/3519270.3538421},
    Year = {2022},
    bdsk-url-1 = {https://doi.org/10.1145/3519270.3538421},
    date-added = {2022-07-26 08:23:22 +0200},
    date-modified = {2022-07-26 08:23:22 +0200},
    numpages = {8},
    doi = {10.1145/3519270.3538421}
}

@inproceedings{10.1145/3519270.3538421, Abstract = {Population protocols are a model of computation in which an arbitrary number of anonymous finite-memory agents are interacting in order to decide by stable consensus a predicate. In this paper, we focus on the counting predicates that asks, given an initial configuration, whether the number of agents in some initial state i is at least n. In 2018, Blondin, Esparza, and Jaax shown that with a fix number of leaders, there exists infinitely many n for which the counting predicate is stably computable by a protocol with at most O(log log(n)) states. We provide in this paper a matching lower-bound (up to a square root) that improves the inverse-Ackermannian lower-bound presented at PODC in 2021.}, Address = {New York, NY, USA}, Author = {Leroux, J\'{e}r\^{o}me}, BookTitle = {Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing}, File = {State Complexity of Protocols With Leaders - 3519270.3538421.pdf}, ISBN = {9781450392624}, Keywords = {petri nets, counting predicates, state complexity, population protocols}, Location = {Salerno, Italy}, Pages = {257--264}, Publisher = {Association for Computing Machinery}, Series = {PODC'22}, Title = {State Complexity of Protocols with Leaders}, URL = {https://doi.org/10.1145/3519270.3538421}, Year = {2022}, bdsk-url-1 = {https://doi.org/10.1145/3519270.3538421}, date-added = {2022-07-26 08:23:22 +0200}, date-modified = {2022-07-26 08:23:22 +0200}, numpages = {8}, doi = {10.1145/3519270.3538421} }