{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:50:40Z","timestamp":1782971440028,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T00:00:00Z","timestamp":1596585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T00:00:00Z","timestamp":1596585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P 27613"],"award-info":[{"award-number":["P 27613"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M005038\/1"],"award-info":[{"award-number":["EP\/M005038\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of <jats:italic>n<\/jats:italic> identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebasti\u00e1n, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size <jats:italic>n<\/jats:italic>), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.<\/jats:p>","DOI":"10.1007\/s00446-020-00385-0","type":"journal-article","created":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T07:02:32Z","timestamp":1596610952000},"page":"91-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Time-space trade-offs in population protocols for the majority problem"],"prefix":"10.1007","volume":"34","author":[{"given":"Petra","family":"Berenbrink","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Els\u00e4sser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom","family":"Friedetzky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"Kaaser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0000-8689","authenticated-orcid":false,"given":"Peter","family":"Kling","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz","family":"Radzik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,8,5]]},"reference":[{"key":"385_CR1","doi-asserted-by":"publisher","unstructured":"Alistarh, D., Gelashvili, R., Vojnovic, M.: Fast and exact majority in population protocols. In: Georgiou, C., Spirakis, P.G. (eds.) Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, July 21 \u201323, 2015, pp. 47\u201356. ACM (2015). https:\/\/doi.org\/10.1145\/2767386.2767429","DOI":"10.1145\/2767386.2767429"},{"key":"385_CR2","doi-asserted-by":"publisher","unstructured":"Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 2560\u20132579. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.169","DOI":"10.1137\/1.9781611974782.169"},{"key":"385_CR3","doi-asserted-by":"publisher","unstructured":"Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018, pp. 2221\u20132239. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.144","DOI":"10.1137\/1.9781611975031.144"},{"key":"385_CR4","doi-asserted-by":"publisher","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: Chaudhuri, S., Kutten, S. (eds.) Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John\u2019s, Newfoundland, Canada, July 25\u201328, 2004, pp. 290\u2013299. ACM (2004). https:\/\/doi.org\/10.1145\/1011767.1011810","DOI":"10.1145\/1011767.1011810"},{"issue":"4","key":"385_CR5","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). https:\/\/doi.org\/10.1007\/s00446-005-0138-3","journal-title":"Distrib. Comput."},{"key":"385_CR6","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proc. PODC, pp. 292\u2013299, New York (2006)","DOI":"10.1145\/1146381.1146425"},{"issue":"4","key":"385_CR7","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."},{"issue":"2","key":"385_CR8","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). https:\/\/doi.org\/10.1007\/s00446-008-0059-z","journal-title":"Distrib. Comput."},{"issue":"3","key":"385_CR9","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). https:\/\/doi.org\/10.1007\/s00446-008-0067-z","journal-title":"Distrib. Comput."},{"key":"385_CR10","first-page":"98","volume":"93","author":"J Aspnes","year":"2007","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. Bull. Euro. Assoc. Theor. Comput. Sci. 93, 98\u2013117 (2007)","journal-title":"Bull. Euro. Assoc. Theor. Comput. Sci."},{"key":"385_CR11","doi-asserted-by":"publisher","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: Schmid, U., Widder, J. (eds.) 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 of LIPIcs, pp. 10:1\u201310:18. Schloss Dagstuhl -Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.10","DOI":"10.4230\/LIPIcs.DISC.2018.10"},{"key":"385_CR12","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Friedetzky, T., Kaaser, D., Kling,P.: Tight & simple load balancing (2019). accepted at IPDPS 2019. An earlier version can be found under the arXiv ID arXiv:1808.05389 [cs.DC]","DOI":"10.1109\/IPDPS.2019.00080"},{"key":"385_CR13","doi-asserted-by":"publisher","unstructured":"Bilke, A., Cooper, C., Els\u00e4sser, R., Radzik, T.: Brief announcement: Population protocols for leader election and exact majority with O(log($${}^{\\text{2}}$$) n) states and O(log($${}^{\\text{2 }}$$) n) convergence time. In: Schiller, E.M., Schwarzmann, A.A. (eds.) Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pp. 451\u2013453. ACM (2017). https:\/\/doi.org\/10.1145\/3087801.3087858","DOI":"10.1145\/3087801.3087858"},{"key":"385_CR14","doi-asserted-by":"publisher","unstructured":"Doty, D., Eftekhari, M.: Efficient size estimation and impossibility of termination in uniform dense population protocols. In: Robinson, P., Ellen, F. (eds.) In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pp. 34\u201342. ACM (2019). https:\/\/doi.org\/10.1145\/3293611.3331627","DOI":"10.1145\/3293611.3331627"},{"key":"385_CR15","unstructured":"Doty, D., Eftekhari, M., Michail, O., Spirakis, P.G., Theofilatos, M.: Exact size counting in uniform population protocols in nearly logarithmic time. CoRR, abs\/1805.04832 (2018). URL http:\/\/arxiv.org\/abs\/1805.04832"},{"issue":"3","key":"385_CR16","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/110823018","volume":"50","author":"M Draief","year":"2012","unstructured":"Draief, M., Vojnovic, M.: Convergence speed of binary interval consensus. SIAM J. Control Optim. 50(3), 1087\u20131109 (2012). https:\/\/doi.org\/10.1137\/110823018","journal-title":"SIAM J. Control Optim."},{"key":"385_CR17","unstructured":"Els\u00e4sser, R., Radzik, T.: Recent results in population protocols for exact majority and leader election. Bull. EATCS 126 (2018). URL http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/549\/546"},{"key":"385_CR18","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Stachowiak, G.: Fast space optimal leader election in population protocols. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018, pp. 2653\u20132667. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.169","DOI":"10.1137\/1.9781611975031.169"},{"key":"385_CR19","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Uznanski, P.: Brief announcement: Population protocols are fast. In: Newport, C., Keidar, I. (eds.) Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pp. 475\u2013477. ACM (2018). URL https:\/\/dl.acm.org\/citation.cfm?id=3212788","DOI":"10.1145\/3212734.3212788"},{"key":"385_CR20","doi-asserted-by":"publisher","unstructured":"Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C.L., Spirakis, P.G.: Determining majority in networks with local interactions and very small local memory. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming \u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pp. 871\u2013882. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_72","DOI":"10.1007\/978-3-662-43948-7_72"},{"key":"385_CR21","doi-asserted-by":"publisher","unstructured":"Mocquard, Y., Anceaume, E., Aspnes, J., Busnel, Y., Sericola, B.: Counting with population protocols. In: Avresky, D.R., Busnel, Y. (eds.) 14th IEEE International Symposium on Network Computing and Applications, NCA 2015, Cambridge, MA, USA, September 28\u201330, 2015, pp. 35\u201342. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/NCA.2015.35","DOI":"10.1109\/NCA.2015.35"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00385-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00385-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00385-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T23:44:09Z","timestamp":1628120649000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00385-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,5]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["385"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00385-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,5]]},"assertion":[{"value":"19 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}