{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T05:09:43Z","timestamp":1764133783771,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":18,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["1844976"],"award-info":[{"award-number":["1844976"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["1900931"],"award-info":[{"award-number":["1900931"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467942","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"77-80","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority"],"prefix":"10.1145","author":[{"given":"David","family":"Doty","sequence":"first","affiliation":[{"name":"University of California, Davis, Davis, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahsa","family":"Eftekhari","sequence":"additional","affiliation":[{"name":"University of California, Davis, Davis, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leszek","family":"G\u0105sieniec","sequence":"additional","affiliation":[{"name":"University of Liverpool, Liverpool, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Severson","sequence":"additional","affiliation":[{"name":"University of California, Davis, Davis, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grzegorz","family":"Stachowiak","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Przemyslaw","family":"Uzna\u0144ski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"https:\/\/github.com\/UC-Davis-molecular-computing\/ppsim\/blob\/main\/examples\/majority.ipynb.  https:\/\/github.com\/UC-Davis-molecular-computing\/ppsim\/blob\/main\/examples\/majority.ipynb."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.169"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175449"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767429"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0067-z"},{"key":"e_1_3_2_2_7_1","first-page":"191","volume-title":"PODC 2020: Proceedings of the 39th Symposium on Principles of Distributed Computing","author":"Ben-Nun Stav","year":"2020","unstructured":"Stav Ben-Nun , Tsvi Kopelowitz , Matan Kraus , and Ely Porat . An O(log 3\/2 n) parallel time population protocol for majority with O(log n) states . In PODC 2020: Proceedings of the 39th Symposium on Principles of Distributed Computing , pages 191 -- 199 , 2020 . Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, and Ely Porat. An O(log 3\/2 n) parallel time population protocol for majority with O(log n) states. In PODC 2020: Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 191--199, 2020."},{"key":"e_1_3_2_2_8_1","first-page":"1","volume-title":"DISC 2018: Proceedings of the 32nd International Symposium on Distributed Computing","volume":"10","author":"Berenbrink Petra","year":"2018","unstructured":"Petra Berenbrink , Robert Els\"asser, Tom Friedetzky , Dominik Kaaser , Peter Kling , and Tomasz Radzik . A population protocol for exact majority with O(log 5\/3 n) stabilization time and ?(log n) states . In DISC 2018: Proceedings of the 32nd International Symposium on Distributed Computing , volume 10 , pages 1 -- 18 , 2018 . Petra Berenbrink, Robert Els\"asser, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A population protocol for exact majority with O(log 5\/3 n) stabilization time and ?(log n) states. In DISC 2018: Proceedings of the 32nd International Symposium on Distributed Computing, volume 10, pages 1--18, 2018."},{"key":"e_1_3_2_2_9_1","volume-title":"Distributed Computing","author":"Berenbrink Petra","year":"2020","unstructured":"Petra Berenbrink , Robert Els\u00e4sser , Tom Friedetzky , Dominik Kaaser , Peter Kling , and Tomasz Radzik . Time-space trade-offs in population protocols for the majority problem . Distributed Computing , Aug 2020 . Petra Berenbrink, Robert Els\u00e4sser, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority problem. Distributed Computing, Aug 2020."},{"key":"e_1_3_2_2_10_1","first-page":"451","volume-title":"PODC 2017: Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Bilke Andreas","year":"2017","unstructured":"Andreas Bilke , Colin Cooper , Robert Els\u00e4sser , and Tomasz Radzik . Brief announcement : Population protocols for leader election and exact majority with O(log 2 n) states and O(log 2 n) convergence time . In PODC 2017: Proceedings of the ACM Symposium on Principles of Distributed Computing , pages 451 -- 453 . ACM, 2017 . Andreas Bilke, Colin Cooper, Robert Els\u00e4sser, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log 2 n) states and O(log 2 n) convergence time. In PODC 2017: Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 451--453. ACM, 2017."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.001"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331627"},{"key":"e_1_3_2_2_13_1","volume-title":"DISC 2018:  32nd International Symposium on Distributed Computing","author":"Doty David","year":"2018","unstructured":"David Doty , Mahsa Eftekhari , Othon Michail , Paul G. Spirakis , and Michail Theofilatos . Brief announcement : Exact size counting in uniform population protocols in nearly logarithmic time . In DISC 2018: 32nd International Symposium on Distributed Computing , 2018 . David Doty, Mahsa Eftekhari, Othon Michail, Paul G. Spirakis, and Michail Theofilatos. Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time. In DISC 2018: 32nd International Symposium on Distributed Computing, 2018."},{"key":"e_1_3_2_2_14_1","series-title":"SIAM Journal on control and Optimization, 50(3):1087--1109","volume-title":"Convergence speed of binary interval consensus","author":"Draief Moez","year":"2012","unstructured":"Moez Draief and Milan Vojnovic . Convergence speed of binary interval consensus . SIAM Journal on control and Optimization, 50(3):1087--1109 , 2012 . Moez Draief and Milan Vojnovic. Convergence speed of binary interval consensus. SIAM Journal on control and Optimization, 50(3):1087--1109, 2012."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.169"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_72"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2015.35"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2016.7778621"}],"event":{"name":"PODC '21: 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":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467942","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467942","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467942","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:11Z","timestamp":1750191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":18,"alternative-id":["10.1145\/3465084.3467942","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467942","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}