{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:50:39Z","timestamp":1782971439539,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T00:00:00Z","timestamp":1686787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T00:00:00Z","timestamp":1686787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial global configuration satisfies a given property, specified as a predicate on the set of configurations. The state complexity of a predicate is the number of states of a smallest protocol that computes it. Previous work by Blondin et al. has shown that the counting predicates <jats:inline-formula><jats:alternatives><jats:tex-math>$$x \\ge \\eta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mi>\u03b7<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> have state complexity <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\log \\eta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>\u03b7<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for leaderless protocols and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\log \\log \\eta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>\u03b7<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of <jats:inline-formula><jats:alternatives><jats:tex-math>$$x \\ge \\eta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mi>\u03b7<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (\\log \\log \\eta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>\u03b7<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.\n<\/jats:p>","DOI":"10.1007\/s00446-023-00450-4","type":"journal-article","created":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T16:02:17Z","timestamp":1686844937000},"page":"209-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower bounds on the state complexity of population protocols"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1786-9592","authenticated-orcid":false,"given":"Philipp","family":"Czerner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9862-4919","authenticated-orcid":false,"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7214-9467","authenticated-orcid":false,"given":"J\u00e9r\u00f4me","family":"Leroux","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,15]]},"reference":[{"key":"450_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2015.07.012","volume":"603","author":"S Abriola","year":"2015","unstructured":"Abriola, S., Figueira, S., Senno, G.: Linearizing well quasi-orders and bounding the length of bad sequences. Theor. Comput. Sci. 603, 3\u201322 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"450_CR2","first-page":"2560","volume-title":"SODA","author":"D Alistarh","year":"2017","unstructured":"Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: SODA, pp. 2560\u20132579. SIAM, Philadelphia (2017)"},{"key":"450_CR3","first-page":"2221","volume-title":"SODA","author":"D Alistarh","year":"2018","unstructured":"Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: SODA, pp. 2221\u20132239. SIAM, Philadelphia (2018)"},{"issue":"3","key":"450_CR4","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/3289137.3289150","volume":"49","author":"D Alistarh","year":"2018","unstructured":"Alistarh, D., Gelashvili, R.: Recent algorithmic advances in population protocols. SIGACT News 49(3), 63\u201373 (2018)","journal-title":"SIGACT News"},{"key":"450_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: PODC, pp 290\u2013299. ACM (2004)","DOI":"10.1145\/1011767.1011810"},{"issue":"4","key":"450_CR6","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"issue":"3","key":"450_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00446-008-0067-z","volume":"21","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distrib. Comput. 21(3), 183\u2013199 (2008)","journal-title":"Distrib. Comput."},{"issue":"4","key":"450_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","volume":"20","author":"D Angluin","year":"2007","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279\u2013304 (2007)","journal-title":"Distrib. Comput."},{"key":"450_CR9","doi-asserted-by":"crossref","unstructured":"Balasubramanian, A.R.: Complexity of controlled bad sequences over finite sets of $$\\mathbb{N}^d$$. In: LICS, pp. 130\u2013140. ACM (2020)","DOI":"10.1145\/3373718.3394753"},{"key":"450_CR10","series-title":"Lecture Notes in Computer Science","volume-title":"FoSSaCS","author":"AR Balasubramanian","year":"2021","unstructured":"Balasubramanian, A.R., Esparza, J., Raskin, M.A.: Finding cut-offs in leaderless rendez-vous protocols is easy. In: FoSSaCS. Lecture Notes in Computer Science, vol. 12650. Springer, New York (2021)"},{"key":"450_CR11","unstructured":"Blondin, M., Esparza, J., Genest, B., Helfrich, M., Jaax, S.: Succinct population protocols for Presburger arithmetic. In: STACS, vol. 154, pp. 40:1\u201340:15. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"450_CR12","unstructured":"Blondin, M., Esparza, J., Jaax, S.: Large flocks of small birds: On the minimal size of population protocols. In STACS, vol.\u00a096, pp. 16:1\u201316:14, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"450_CR13","doi-asserted-by":"crossref","unstructured":"Czerner, P., Esparza, J.: Lower bounds on the state complexity of population protocols. In: PODC, pp. 45\u201354. ACM (2021)","DOI":"10.1145\/3465084.3467912"},{"issue":"1","key":"450_CR14","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/3422822","volume":"68","author":"W Czerwinski","year":"2021","unstructured":"Czerwinski, W., Lasota, S., Lazic, R., Leroux, J., Mazowiecki, F.: The reachability problem for Petri nets is not elementary. J. ACM 68(1), 7:1-7:28 (2021)","journal-title":"J. ACM"},{"key":"450_CR15","unstructured":"Czerwinski, W., Orlikowski, L.: Reachability in vector addition systems is Ackermann-complete. CoRR, arxiv:2104.13866 (2021)"},{"key":"450_CR16","unstructured":"Els\u00e4sser, R., Radzik, T.: Recent results in population protocols for exact majority and leader election. Bull. EATCS 126 (2018)"},{"key":"450_CR17","unstructured":"Esparza, J.: Petri nets lecture notes (2019). https:\/\/archive.model.in.tum.de\/um\/courses\/petri\/SS2019\/PNSkript.pdf"},{"key":"450_CR18","doi-asserted-by":"crossref","unstructured":"Figueira, D., Figueira, S., Schmitz, S., Schnoebelen, P.: Ackermannian and primitive-recursive bounds with Dickson\u2019s lemma. In: LICS, pp. 269\u2013278. IEEE Computer Society (2011)","DOI":"10.1109\/LICS.2011.39"},{"issue":"1","key":"450_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3424659","volume":"68","author":"L G\u0105sieniec","year":"2020","unstructured":"G\u0105sieniec, L., Stachowiak, G.: Enhanced phase clocks, population protocols, and fast space optimal leader election. J. ACM 68(1), 1\u201312 (2020)","journal-title":"J. ACM"},{"issue":"3","key":"450_CR20","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/3242953.3242964","volume":"5","author":"C Haase","year":"2018","unstructured":"Haase, C.: A survival guide to Presburger arithmetic. ACM SIGLOG News 5(3), 67\u201382 (2018)","journal-title":"ACM SIGLOG News"},{"key":"450_CR21","unstructured":"Horn, F., Sangnier, A.: Deciding the existence of cut-off in parameterized rendez-vous networks. In: CONCUR, vol. 171, pp. 46:1\u201346:16. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"450_CR22","unstructured":"Leroux, J.: The reachability problem for Petri nets is not primitive recursive. CoRR arxiv:2104.12695 (2021)"},{"key":"450_CR23","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0304-3975(84)90029-X","volume":"32","author":"K McAloon","year":"1984","unstructured":"McAloon, K.: Petri nets and large finite sets. Theor. Comput. Sci. 32, 173\u2013183 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"450_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-53904-2_94","volume-title":"RTA","author":"L Pottier","year":"1991","unstructured":"Pottier, L.: Minimal solutions of linear diophantine systems: bounds and algorithms. In: RTA. Lecture Notes in Computer Science, vol. 488, pp. 162\u2013173. New York, Springer (1991)"},{"key":"450_CR25","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(78)90036-1","volume":"6","author":"C Rackoff","year":"1978","unstructured":"Rackoff, C.: The covering and boundedness problems for vector addition systems. Theor. Comput. Sci. 6, 223\u2013231 (1978)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"450_CR26","doi-asserted-by":"publisher","first-page":"3;1","DOI":"10.1145\/2858784","volume":"8","author":"S Schmitz","year":"2016","unstructured":"Schmitz, S.: Complexity hierarchies beyond elementary. ACM Trans. Comput. Theory 8(1), 3;1-3:36 (2016)","journal-title":"ACM Trans. Comput. Theory"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00450-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00450-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00450-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T18:03:26Z","timestamp":1690826606000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00450-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,15]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["450"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00450-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,15]]},"assertion":[{"value":"29 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}