{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T08:10:52Z","timestamp":1767773452181,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1844976, 1619343"],"award-info":[{"award-number":["1844976, 1619343"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331627","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"page":"34-42","update-policy":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols"],"prefix":"10.1145","author":[{"given":"David","family":"Doty","sequence":"first","affiliation":[{"name":"University of California, Davis, Davis, CA, USA"}]},{"given":"Mahsa","family":"Eftekhari","sequence":"additional","affiliation":[{"name":"University of California, Davis, Davis, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Scott Aaronson. 2006. Computational Complexity and the Anthropic Principle. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.scottaaronson.com\/talks\/anthropic.html.  Scott Aaronson. 2006. Computational Complexity and the Anthropic Principle. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.scottaaronson.com\/talks\/anthropic.html."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039855"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175449"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_38"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289137.3289150"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767429"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146425"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0067-z"},{"key":"e_1_3_2_1_10_1","volume-title":"Time and Space Optimal Counting in Population Protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS","volume":"70","author":"Aspnes James","year":"2017","unstructured":"James Aspnes , Joffroy Beauquier , Janna Burman , and Devan Sohier . 2017 . Time and Space Optimal Counting in Population Protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016), Vol. 70 . 13:1--13:17. James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. 2017. Time and Space Optimal Counting in Population Protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016), Vol. 70. 13:1--13:17."},{"key":"e_1_3_2_1_11_1","volume-title":"Bulletin of the European Association for Theoretical Computer Science","volume":"93","author":"Aspnes James","year":"2007","unstructured":"James Aspnes and Eric Ruppert . 2007 . An introduction to population protocols . Bulletin of the European Association for Theoretical Computer Science , Vol. 93 (October 2007), 98--117. James Aspnes and Eric Ruppert. 2007. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, Vol. 93 (October 2007), 98--117."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48653-5_42"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301358"},{"key":"e_1_3_2_1_14_1","volume-title":"ICALP 2017: 44th International Colloquium on Automata, Languages, and Programming (LIPIcs)","volume":"80","author":"Belleville Amanda","year":"2017","unstructured":"Amanda Belleville , David Doty , and David Soloveichik . 2017 . Hardness of computing and approximating predicates and functions with leaderless population protocols . In ICALP 2017: 44th International Colloquium on Automata, Languages, and Programming (LIPIcs) , Vol. 80 . 141:1--141:14. Amanda Belleville, David Doty, and David Soloveichik. 2017. Hardness of computing and approximating predicates and functions with leaderless population protocols. In ICALP 2017: 44th International Colloquium on Automata, Languages, and Programming (LIPIcs), Vol. 80. 141:1--141:14."},{"key":"e_1_3_2_1_15_1","volume-title":"Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA","volume":"61","author":"Berenbrink Petra","year":"2018","unstructured":"Petra Berenbrink , Dominik Kaaser , Peter Kling , and Lena Otterbach . 2018 . Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018), Vol. 61 . 9:1--9:11. Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. 2018. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018), Vol. 61. 9:1--9:11."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331631"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087858"},{"volume-title":"Computational modeling of genetic and biochemical networks","author":"Bower James M","key":"e_1_3_2_1_18_1","unstructured":"James M Bower and Hamid Bolouri . 2004. Computational modeling of genetic and biochemical networks . MIT press . James M Bower and Hamid Bolouri. 2004. Computational modeling of genetic and biochemical networks .MIT press."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11476-2_10"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-013-9393-6"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1038\/nnano.2013.189"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2370405"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634131"},{"key":"e_1_3_2_1_24_1","volume-title":"Efficient size estimation and impossibility of termination in uniform dense population protocols. CoRR","author":"Doty David","year":"2018","unstructured":"David Doty and Mahsa Eftekhari . 2018. Efficient size estimation and impossibility of termination in uniform dense population protocols. CoRR , Vol. abs\/ 1808 .08913 ( 2018 ). arxiv: 1808.08913 https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/arxiv.org\/abs\/1808.08913 David Doty and Mahsa Eftekhari. 2018. Efficient size estimation and impossibility of termination in uniform dense population protocols. CoRR, Vol. abs\/1808.08913 (2018). arxiv: 1808.08913 https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/arxiv.org\/abs\/1808.08913"},{"key":"e_1_3_2_1_25_1","volume-title":"32nd International Symposium on Distributed Computing (DISC","author":"Doty David","year":"2018","unstructured":"David Doty , Mahsa Eftekhari , Othon Michail , Paul G. Spirakis , and Michail Theofilatos . 2018 . Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time . In 32nd International Symposium on Distributed Computing (DISC 2018). 46:1--46:3. David Doty, Mahsa Eftekhari, Othon Michail, Paul G. Spirakis, and Michail Theofilatos. 2018. Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time. In 32nd International Symposium on Distributed Computing (DISC 2018). 46:1--46:3."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-014-9435-8"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0281-z"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2007.05.011"},{"key":"e_1_3_2_1_29_1","volume-title":"Fast Space Optimal Leader Election in Population Protocols. In SODA 2018: ACM-SIAM Symposium on Discrete Algorithms .","author":"Gasieniec Leszek","year":"2018","unstructured":"Leszek Gasieniec and Grzegorz Stachowiak . 2018 . Fast Space Optimal Leader Election in Population Protocols. In SODA 2018: ACM-SIAM Symposium on Discrete Algorithms . to appear. Leszek Gasieniec and Grzegorz Stachowiak. 2018. Fast Space Optimal Leader Election in Population Protocols. In SODA 2018: ACM-SIAM Symposium on Discrete Algorithms . to appear."},{"key":"e_1_3_2_1_31_1","volume-title":"Population Protocols Are Fast. CoRR","author":"Kosowski Adrian","year":"2018","unstructured":"Adrian Kosowski and Przemyslaw Uznanski . 2018. Population Protocols Are Fast. CoRR , Vol. abs\/ 1802 .06872 ( 2018 ). arxiv: 1802.06872 https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/arxiv.org\/abs\/1802.06872 Adrian Kosowski and Przemyslaw Uznanski. 2018. Population Protocols Are Fast. CoRR, Vol. abs\/1802.06872 (2018). arxiv: 1802.06872 https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/arxiv.org\/abs\/1802.06872"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767402"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33536-5_8"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2018.8548344"},{"key":"e_1_3_2_1_35_1","unstructured":"Philippe Rigollet. 2015. Lecture Notes for MIT course 18.S997: High Dimensional Statistics. URL: https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/ocw.mit.edu\/courses\/mathematics\/18-s997-high-dimensional-statistics-spring-2015\/lecture-notes\/.  Philippe Rigollet. 2015. Lecture Notes for MIT course 18.S997: High Dimensional Statistics. URL: https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/ocw.mit.edu\/courses\/mathematics\/18-s997-high-dimensional-statistics-spring-2015\/lecture-notes\/."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-008-9067-y"},{"key":"e_1_3_2_1_37_1","volume-title":"Science","volume":"358","author":"Srinivas Niranjan","year":"2017","unstructured":"Niranjan Srinivas , James Parkin , Georg Seelig , Erik Winfree , and David Soloveichik . 2017 . Enzyme-free nucleic acid dynamical systems . Science , Vol. 358 , 6369 (2017), eaal2052. Niranjan Srinivas, James Parkin, Georg Seelig, Erik Winfree, and David Soloveichik. 2017. Enzyme-free nucleic acid dynamical systems. Science, Vol. 358, 6369 (2017), eaal2052."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331585"},{"key":"e_1_3_2_1_39_1","first-page":"31","article-title":"Variazioni e fluttuazioni del numero d'individui in specie animali conviventi","volume":"2","author":"Volterra Vito","year":"1926","unstructured":"Vito Volterra . 1926 . Variazioni e fluttuazioni del numero d'individui in specie animali conviventi . Mem. Acad. Lincei Roma , Vol. 2 (1926), 31 -- 113 . Vito Volterra. 1926. Variazioni e fluttuazioni del numero d'individui in specie animali conviventi. Mem. Acad. Lincei Roma, Vol. 2 (1926), 31--113.","journal-title":"Mem. Acad. Lincei Roma"}],"event":{"name":"PODC '19: 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":"Toronto ON Canada","acronym":"PODC '19"},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3293611.3331627","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331627","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331627","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:02Z","timestamp":1750208522000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3293611.3331627"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":38,"alternative-id":["10.1145\/3293611.3331627","10.1145\/3293611"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/3293611.3331627","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}