{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T21:18:10Z","timestamp":1763414290138,"version":"3.45.0"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032111265","type":"print"},{"value":"9783032111272","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T00:00:00Z","timestamp":1763424000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T00:00:00Z","timestamp":1763424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-11127-2_22","type":"book-chapter","created":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T20:03:41Z","timestamp":1763409821000},"page":"270-286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time and\u00a0Space-Optimal Silent Self-stabilizing Exact Majority in\u00a0Population Protocols"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8102-0280","authenticated-orcid":false,"given":"Haruki","family":"Kanaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4836-2903","authenticated-orcid":false,"given":"Ryota","family":"Eguchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2144-4949","authenticated-orcid":false,"given":"Taisho","family":"Sasada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9400-1095","authenticated-orcid":false,"given":"Fukuhito","family":"Ooshita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9837-5147","authenticated-orcid":false,"given":"Michiko","family":"Inoue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,18]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2221\u20132239 (2018)","DOI":"10.1137\/1.9781611975031.144"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Gelashvili, R., Vojnovi\u0107, M.: Fast and exact majority in population protocols. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 47\u201356 (2015)","DOI":"10.1145\/2767386.2767429"},{"issue":"4","key":"22_CR3","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."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Distributed Computing, pp. 61\u201375 (2006)","DOI":"10.1007\/11864219_5"},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00446-008-0059-z","volume":"21","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: A simple population protocol for fast robust approximate majority. Distrib. Comput. 21(2), 87\u2013102 (2008)","journal-title":"Distrib. Comput."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Bankhamer, G., et al.: Population protocols for exact plurality consensus: How a small chance of failure helps to eliminate insignificant opinions. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pp. 224\u2013234 (2022)","DOI":"10.1145\/3519270.3538447"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Nun, S., Kopelowitz, T., Kraus, M., Porat, E.: An O(log3\/2 n) parallel time population protocol for majority with O(log n) states. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC \u201920, New York, NY, USA, pp. 191\u2013199 (2020)","DOI":"10.1145\/3382734.3405747"},{"key":"22_CR8","unstructured":"Berenbrink, P., Biermeier, F., Hahn, C., Kaaser, D.: Loosely-stabilizing phase clocks and the adaptive majority problem. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), vol.\u00a0221, pp. 7:1\u20137:17 (2022)"},{"key":"22_CR9","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T., Kaaser, D., Kling, P., Radzik, T.: A population protocol for exact majority with O(log5\/3 n) stabilization time and theta(log n) states. In: 32nd International Symposium on Distributed Computing (DISC 2018), vol.\u00a0121, pp. 10:1\u201310:18 (2018)"},{"issue":"2","key":"22_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00446-020-00385-0","volume":"34","author":"P Berenbrink","year":"2021","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T., Kaaser, D., Kling, P., Radzik, T.: Time-space trade-offs in population protocols for the majority problem. Distrib. Comput. 34(2), 91\u2013111 (2021)","journal-title":"Distrib. Comput."},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Bilke, A., Cooper, C., Els\u00e4sser, R., Radzik, T.: Brief announcement: population protocols for leader election and exact majority with O(log2 n) states and O(log2 n) convergence time. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 451\u2013453 (2017)","DOI":"10.1145\/3087801.3087858"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Burman, J., et al.: Time-optimal self-stabilizing leader election in population protocols. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC\u201921, pp. 33\u201344 (2021)","DOI":"10.1145\/3465084.3467898"},{"issue":"3","key":"22_CR13","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00224-011-9313-z","volume":"50","author":"S Cai","year":"2012","unstructured":"Cai, S., Izumi, T., Wada, K.: How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory Comput. Syst. 50(3), 433\u2013445 (2012)","journal-title":"Theory Comput. Syst."},{"key":"22_CR14","unstructured":"Chatzigiannakis, I., Dolev, S., Fekete, S., Michail, O., Spirakis, P.: On the fairness of probabilistic schedulers for population protocols. In: Algorithmic Methods for Distributed Cooperative Systems, vol.\u00a09371, pp. 1\u201323 (2010)"},{"issue":"1","key":"22_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s11047-019-09756-4","volume":"19","author":"A Condon","year":"2020","unstructured":"Condon, A., Hajiaghayi, M., Kirkpatrick, D., Ma\u0148uch, J.: Approximate majority analyses using tri-molecular chemical reaction networks. Nat. Comput. 19(1), 249\u2013270 (2020)","journal-title":"Nat. Comput."},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Doty, D., Eftekhari, M., G$$\\upalpha $$asieniec, L., Severson, E., Uzna\u0144ski, P., Stachowiak, G.: A time and space optimal stable population protocol solving exact majority. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1044\u20131055 (2022)","DOI":"10.1109\/FOCS52979.2021.00104"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Draief, M., Vojnovic, M.: Convergence speed of binary interval consensus. In: 2010 Proceedings IEEE INFOCOM, pp.\u00a01\u20139 (2010)","DOI":"10.1109\/INFCOM.2010.5461999"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"G\u0105sieniec, L., Grodzicki, T., Stachowiak, G.: Near-state and state-optimal self-stabilising leader election population protocols (2025). https:\/\/arxiv.org\/abs\/2502.01227","DOI":"10.1145\/3732772.3733528"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Uznanski, P.: Brief announcement: population protocols are fast. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC \u201918, pp. 475\u2013477 (2018)","DOI":"10.1145\/3212734.3212788"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)","DOI":"10.1017\/CBO9780511813603"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Mocquard, Y., Anceaume, E., Aspnes, J., Busnel, Y., Sericola, B.: Counting with population protocols. In: 2015 IEEE 14th International Symposium on Network Computing and Applications (2015)","DOI":"10.1109\/NCA.2015.35"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Mocquard, Y., Anceaume, E., Sericola, B.: Optimal proportion computation with population protocols. In: 2016 IEEE 15th International Symposium on Network Computing and Applications (NCA), pp. 216\u2013223 (2016)","DOI":"10.1109\/NCA.2016.7778621"},{"key":"22_CR23","doi-asserted-by":"crossref","unstructured":"Perron, E., Vasudevan, D., Vojnovic, M.: Using three states for binary consensus on complete graphs. In: IEEE INFOCOM 2009, pp. 2527\u20132535 (2009)","DOI":"10.1109\/INFCOM.2009.5062181"},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2012.01.007","volume":"444","author":"Y Sudo","year":"2012","unstructured":"Sudo, Y., Nakamura, J., Yamauchi, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Loosely-stabilizing leader election in a population protocol model. Theor. Comput. Sci. 444, 100\u2013112 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Yasumi, H., Ooshita, F., Yamaguchi, K., Inoue, M.: Space-optimal population protocols for uniform bipartition under global fairness. IEICE Trans. Inf. Syst. E102.D(3), 454\u2013463 (2019)","DOI":"10.1587\/transinf.2018FCP0009"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11127-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T20:03:53Z","timestamp":1763409833000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11127-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,18]]},"ISBN":["9783032111265","9783032111272"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11127-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,18]]},"assertion":[{"value":"18 November 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kathmandu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nepal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}