{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:55Z","timestamp":1750220335594,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":17,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0028"],"award-info":[{"award-number":["ANR-17-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538421","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"257-264","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["State Complexity of Protocols with Leaders"],"prefix":"10.1145","author":[{"given":"J\u00e9r\u00f4me","family":"Leroux","sequence":"first","affiliation":[{"name":"LaBRI, CNRS, Univ. Bordeaux, Talence, France"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Alistarh Dan","year":"1974","unstructured":"Dan Alistarh , James Aspnes , David Eisenstat , Rati Gelashvili , and Ronald L. Rivest . 2017. Time-Space Trade-offs in Population Protocols . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16--19, Philip N. Klein (Ed.). SIAM, 2560--2579. https:\/\/doi.org\/10.1137\/1.978161 1974 782.169 10.1137\/1.9781611974782.169 Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. 2017. Time-Space Trade-offs in Population Protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16--19, Philip N. Klein (Ed.). SIAM, 2560--2579. https:\/\/doi.org\/10.1137\/1.9781611974782.169"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011810"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146425"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0040-2"},{"key":"e_1_3_2_2_6_1","volume-title":"Succinct Population Protocols for Presburger Arithmetic. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020","volume":"15","author":"Blondin Michael","year":"2020","unstructured":"Michael Blondin , Javier Esparza , Blaise Genest , Martin Helfrich , and Stefan Jaax . 2020 . Succinct Population Protocols for Presburger Arithmetic. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 , March 10 --13 , 2020, Montpellier, France (LIPIcs, Vol. 154), Christophe Paul and Markus Bl\"a ser (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 40:1--40: 15 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.40 10.4230\/LIPIcs.STACS.2020.40 Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, and Stefan Jaax. 2020. Succinct Population Protocols for Presburger Arithmetic. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10--13, 2020, Montpellier, France (LIPIcs, Vol. 154), Christophe Paul and Markus Bl\"a ser (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 40:1--40:15. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.40"},{"key":"e_1_3_2_2_7_1","volume-title":"Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018","volume":"14","author":"Blondin Michael","year":"2018","unstructured":"Michael Blondin , Javier Esparza , and Stefan Jaax . 2018 . Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 , February 28 to March 3, 2018, Caen, France (LIPIcs, Vol. 96), Rolf Niedermeier and Brigitte Vall\u00e9e (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 16:1--16: 14 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.16 10.4230\/LIPIcs.STACS.2018.16 Michael Blondin, Javier Esparza, and Stefan Jaax. 2018. Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France (LIPIcs, Vol. 96), Rolf Niedermeier and Brigitte Vall\u00e9e (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 16:1--16:14. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.16"},{"key":"#cr-split#-e_1_3_2_2_8_1.1","unstructured":"Philipp Czerner. 2022. Leaderless Population Protocols Decide Double-exponential Thresholds. https:\/\/doi.org\/10.48550\/ARXIV.2204.02115 10.48550\/ARXIV.2204.02115"},{"key":"#cr-split#-e_1_3_2_2_8_1.2","doi-asserted-by":"crossref","unstructured":"Philipp Czerner. 2022. Leaderless Population Protocols Decide Double-exponential Thresholds. https:\/\/doi.org\/10.48550\/ARXIV.2204.02115","DOI":"10.1145\/3583668.3594571"},{"key":"e_1_3_2_2_9_1","volume-title":"Lower Bounds on the State Complexity of Population Protocols. In PODC '21: ACM Symposium on Principles of Distributed Computing","author":"Czerner Philipp","year":"2021","unstructured":"Philipp Czerner and Javier Esparza . 2021 . Lower Bounds on the State Complexity of Population Protocols. In PODC '21: ACM Symposium on Principles of Distributed Computing , Virtual Event, Italy, July 26--30 , 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 45--54. https:\/\/doi.org\/10.1145\/3465084.3467912 10.1145\/3465084.3467912 Philipp Czerner and Javier Esparza. 2021. Lower Bounds on the State Complexity of Population Protocols. In PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26--30, 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 45--54. https:\/\/doi.org\/10.1145\/3465084.3467912"},{"key":"e_1_3_2_2_10_1","volume-title":"Reachability in Vector Addition Systems is Ackermann-complete. CoRR","author":"Czerwinski Wojciech","year":"2021","unstructured":"Wojciech Czerwinski and Lukasz Orlikowski . 2021. Reachability in Vector Addition Systems is Ackermann-complete. CoRR , Vol. abs\/ 2104 .13866 ( 2021 ). showeprint[arXiv]2104.13866 https:\/\/arxiv.org\/abs\/2104.13866 Wojciech Czerwinski and Lukasz Orlikowski. 2021. Reachability in Vector Addition Systems is Ackermann-complete. CoRR, Vol. abs\/2104.13866 (2021). showeprint[arXiv]2104.13866 https:\/\/arxiv.org\/abs\/2104.13866"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188818"},{"key":"e_1_3_2_2_12_1","volume-title":"Verification of Population Protocols. In 26th International Conference on Concurrency Theory, CONCUR 2015","volume":"482","author":"Esparza Javier","year":"2015","unstructured":"Javier Esparza , Pierre Ganty , J\u00e9 r\u00f4 me Leroux, and Rupak Majumdar. 2015 . Verification of Population Protocols. In 26th International Conference on Concurrency Theory, CONCUR 2015 , Madrid, Spain, September 1.4 , 2015 (LIPIcs, Vol. 42), Luca Aceto and David de Frutos-Escrig (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 470-- 482 . https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2015.470 10.4230\/LIPIcs.CONCUR.2015.470 Javier Esparza, Pierre Ganty, J\u00e9 r\u00f4 me Leroux, and Rupak Majumdar. 2015. Verification of Population Protocols. In 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1.4, 2015 (LIPIcs, Vol. 42), Luca Aceto and David de Frutos-Escrig (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 470--482. https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2015.470"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0272-3"},{"key":"e_1_3_2_2_14_1","volume-title":"The Reachability Problem for Petri Nets is Not Primitive Recursive. CoRR","author":"Leroux J\u00e9","year":"2021","unstructured":"J\u00e9 r\u00f4 me Leroux . 2021. The Reachability Problem for Petri Nets is Not Primitive Recursive. CoRR , Vol. abs\/ 2104 .12695 ( 2021 ). showeprint[arXiv]2104.12695 https:\/\/arxiv.org\/abs\/2104.12695 J\u00e9 r\u00f4 me Leroux. 2021. The Reachability Problem for Petri Nets is Not Primitive Recursive. CoRR, Vol. abs\/2104.12695 (2021). showeprint[arXiv]2104.12695 https:\/\/arxiv.org\/abs\/2104.12695"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-53904-2_94"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90036-1"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538421","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":17,"alternative-id":["10.1145\/3519270.3538421","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538421","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}