{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:00:31Z","timestamp":1760709631943,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,6,6]],"date-time":"2018-06-06T00:00:00Z","timestamp":1528243200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"INRIA project GANG"},{"name":"ANR project DISPLEXITY"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00446-018-0335-5","type":"journal-article","created":{"date-parts":[[2018,6,6]],"date-time":"2018-06-06T07:42:39Z","timestamp":1528270959000},"page":"257-276","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Noisy rumor spreading and plurality consensus"],"prefix":"10.1007","volume":"32","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8755-3892","authenticated-orcid":false,"given":"Emanuele","family":"Natale","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,6,6]]},"reference":[{"key":"335_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2014.07.026","volume":"180","author":"MA Abdullah","year":"2015","unstructured":"Abdullah, M.A., Draief, M.: Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Appl. Math. 180, 1\u201310 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"6014","key":"335_CR2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1126\/science.1193210","volume":"331","author":"Y Afek","year":"2011","unstructured":"Afek, Y., Alon, N., Barad, O., Barkai, N., Bar-Joseph, Z., Hornstein, E.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183\u2013185 (2011)","journal-title":"Science"},{"issue":"4","key":"335_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00446-012-0175-7","volume":"26","author":"Y Afek","year":"2013","unstructured":"Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. Distrib. Comput. 26(4), 195\u2013208 (2013)","journal-title":"Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2221\u20132239 (2018)","key":"335_CR4","DOI":"10.1137\/1.9781611975031.144"},{"issue":"4","key":"335_CR5","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1016\/j.anbehav.2004.01.009","volume":"68","author":"J-M Ame","year":"2004","unstructured":"Ame, J.-M., Rivault, C., Deneubourg, J.-L.: Cockroach aggregation based on strain odour recognition. Anim. Behav. 68(4), 793\u2013801 (2004)","journal-title":"Anim. Behav."},{"issue":"4","key":"335_CR6","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":"335_CR7","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."},{"doi-asserted-by":"crossref","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Middleware for Network Eccentric and Mobile Applications. Springer, pp.\u00a097\u2013120 (2009)","key":"335_CR8","DOI":"10.1007\/978-3-540-89707-1_5"},{"doi-asserted-by":"crossref","unstructured":"Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R.: Plurality consensus in the gossip model. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp.\u00a0371\u2013390 (2015)","key":"335_CR9","DOI":"10.1137\/1.9781611973730.27"},{"issue":"4","key":"335_CR10","first-page":"1","volume":"30","author":"L Becchetti","year":"2016","unstructured":"Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R., Trevisan, L.: Simple dynamics for plurality consensus. Distrib. Comput. 30(4), 1\u201314 (2016)","journal-title":"Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Ben-Shahar, O., Dolev, S., Dolgin, A., Segal, M.: Direction election in flocking swarms. In: Proceedings of the 6th International Workshop on Foundations of Mobile Computing, ACM, pp.\u00a073\u201380 (2010)","key":"335_CR11","DOI":"10.1145\/1860684.1860700"},{"unstructured":"Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Wastell, C.: Plurality consensus in arbitrary graphs: lessons learned from load balancing. In: Proceedings of the 24th Annual European Symposium on Algorithms, vol. 57, p. 10:1\u201310:18 (2016)","key":"335_CR12"},{"unstructured":"Boczkowski, L., Korman, A., Natale, E.: Limits for Rumor Spreading in Stochastic Populations. In: Proceedings of the 9th Innovations in Theoretical Computer Science Conference, vol. 94, pp. 49:1\u201349:21 (2018)","key":"335_CR13"},{"doi-asserted-by":"crossref","unstructured":"Boczkowski, L., Korman, A., Natale, E.: Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 2540\u20132559 (2017)","key":"335_CR14","DOI":"10.1137\/1.9781611974782.168"},{"key":"335_CR15","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1038\/srep00656","volume":"2","author":"L Cardelli","year":"2011","unstructured":"Cardelli, L., Csik\u00e1sz-Nagy, A.: The cell cycle switch computes approximate majority. Sci. Rep. 2, 656\u2013656 (2011)","journal-title":"Sci. Rep."},{"doi-asserted-by":"crossref","unstructured":"Chazelle, B.: Natural algorithms. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp.\u00a0422\u2013431 (2009)","key":"335_CR16","DOI":"10.1137\/1.9781611973068.47"},{"issue":"6919","key":"335_CR17","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1038\/nature01294","volume":"421","author":"L Conradt","year":"2003","unstructured":"Conradt, L., Roper, T.J.: Group decision-making in animals. Nature 421(6919), 155\u2013158 (2003)","journal-title":"Nature"},{"doi-asserted-by":"crossref","unstructured":"Cooper, C., Els\u00e4sser, R., Radzik, T.: The power of two choices in distributed voting. In: Automata, Languages, and Programming, vol.\u00a08573 of Lecture Notes in Computer Science. Springer, pp.\u00a0435\u2013446 (2014)","key":"335_CR18","DOI":"10.1007\/978-3-662-43951-7_37"},{"doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, ACM, pp.\u00a01\u201312 (1987)","key":"335_CR19","DOI":"10.1145\/41840.41841"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Goldberg, L.A., Minder, L., Sauerwald, T., Scheideler, C.: Stabilizing consensus with the power of two choices. In: Proceedings of the 23th Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, pp.\u00a0149\u2013158 (2011)","key":"335_CR20","DOI":"10.1145\/1989493.1989516"},{"issue":"3","key":"335_CR21","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)","journal-title":"SIAM J. Control Optim."},{"key":"335_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"335_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139030687","volume-title":"Network Information Theory","author":"A Gamal El","year":"2011","unstructured":"El Gamal, A., Kim, Y.-H.: Network Information Theory. Cambridge University Press, Cambridge (2011)"},{"doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R., Friedetzky, T., Kaaser, D., Mallmann-Trenn, F., Trinker, H.: Brief announcement: rapid asynchronous plurality consensus. In: Proceedings of the 37th ACM Symposium on Principles of Distributed Computing, ACM, pp. 363\u2013365 (2017)","key":"335_CR24","DOI":"10.1145\/3087801.3087860"},{"doi-asserted-by":"crossref","unstructured":"Feinerman, O., Haeupler, B., Korman, A.: Breathe before speaking: Efficient information dissemination despite noisy, limited and anonymous communication. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing, ACM, pp.\u00a0114\u2013123. Extended abstract of [27] (2014)","key":"335_CR25","DOI":"10.1145\/2611462.2611469"},{"issue":"5","key":"335_CR26","first-page":"1","volume":"30","author":"O Feinerman","year":"2015","unstructured":"Feinerman, O., Haeupler, B., Korman, A.: Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. Distrib. Comput. 30(5), 1\u201317 (2015)","journal-title":"Distrib. Comput."},{"issue":"1427","key":"335_CR27","doi-asserted-by":"publisher","first-page":"1567","DOI":"10.1098\/rstb.2002.1066","volume":"357","author":"NR Franks","year":"2002","unstructured":"Franks, N.R., Pratt, S.C., Mallon, E.B., Britton, N.F., Sumpter, D.J.: Information flow, opinion polling and collective intelligence in house-hunting social insects. Philos. Trans. R. Soc. Lond. B Biol. Sci. 357(1427), 1567\u20131583 (2002)","journal-title":"Philos. Trans. R. Soc. Lond. B Biol. Sci."},{"issue":"1532","key":"335_CR28","doi-asserted-by":"publisher","first-page":"2457","DOI":"10.1098\/rspb.2003.2527","volume":"270","author":"NR Franks","year":"2003","unstructured":"Franks, N.R., Dornhaus, A., Fitzsimmons, J.P., Stevens, M.: Speed versus accuracy in collective decision making. Proc. Biol. Sci. 270(1532), 2457\u20132463 (2003)","journal-title":"Proc. Biol. Sci."},{"doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Parter, M.: A polylogarithmic gossip algorithm for plurality consensus. In: Proceedings of the 36th ACM Symposium on Principles of Distributed Computing, ACM, pp. 117\u2013126 (2016)","key":"335_CR29","DOI":"10.1145\/2933057.2933097"},{"unstructured":"Giakkoupis, G., Berenbrink, P., Friedetzky, T., Kling, P.: Efficient Plurality Consensus, or: the benefits of cleaning up from time to time. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming vol. 55, p. 136:1\u2013136:14 (2016)","key":"335_CR30"},{"doi-asserted-by":"crossref","unstructured":"Jung, K., Kim, B.Y., Vojnovi\u0107, M.: Distributed ranking in networks with limited memory and communication. In: Proceedings of the 2012 IEEE International Symposium on Information Theory, IEEE, pp.\u00a0980\u2013984 (2012)","key":"335_CR31","DOI":"10.1109\/ISIT.2012.6284710"},{"unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE, pp.\u00a0565\u2013574 (2000)","key":"335_CR32"},{"unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the 44st Annual Symposium on Foundations of Computer Science, IEEE, pp.\u00a0482\u2013491 (2003)","key":"335_CR33"},{"issue":"10","key":"335_CR34","doi-asserted-by":"publisher","first-page":"e1003862","DOI":"10.1371\/journal.pcbi.1003862","volume":"10","author":"A Korman","year":"2014","unstructured":"Korman, A., Greenwald, E., Feinerman, O.: Confidence sharing: an economic strategy for efficient information flows in animal groups. PLoS Comput. Biol. 10(10), e1003862\u2013e1003862 (2014)","journal-title":"PLoS Comput. Biol."},{"issue":"25","key":"335_CR35","doi-asserted-by":"publisher","first-page":"5148","DOI":"10.1103\/PhysRevLett.74.5148","volume":"74","author":"M Land","year":"1995","unstructured":"Land, M., Belew, R.: No perfect two-state cellular automata for density classification exists. Phys. Rev. Lett. 74(25), 5148\u20135150 (1995)","journal-title":"Phys. Rev. Lett."},{"key":"335_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"doi-asserted-by":"crossref","unstructured":"Perron, E., Vasudevan, D., Vojnovic, M.: Using three states for binary consensus on complete graphs. In: Proceedings of 28th IEEE INFOCOM (2009)","key":"335_CR37","DOI":"10.1109\/INFCOM.2009.5062181"},{"issue":"1","key":"335_CR38","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1137\/0147013","volume":"47","author":"B Pittel","year":"1987","unstructured":"Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213\u2013223 (1987)","journal-title":"SIAM J. Appl. Math."},{"key":"335_CR39","first-page":"26","volume":"62","author":"H Robbins","year":"1955","unstructured":"Robbins, H.: A remark on Stirling\u2019s formula. Am. Math. Mon. 62, 26\u201329 (1955)","journal-title":"Am. Math. Mon."},{"issue":"1","key":"335_CR40","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s002650050536","volume":"45","author":"TD Seeley","year":"1999","unstructured":"Seeley, T.D., Buhrman, S.C.: Group decision making in swarms of honey bees. Behav. Ecol. Sociobiol. 45(1), 19\u201331 (1999)","journal-title":"Behav. Ecol. Sociobiol."},{"issue":"6","key":"335_CR41","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/s00265-004-0814-5","volume":"56","author":"TD Seeley","year":"2004","unstructured":"Seeley, T.D., Visscher, P.K.: Quorum sensing during nest-site selection by honeybee swarms. Behav. Ecol. Sociobiol. 56(6), 594\u2013601 (2004)","journal-title":"Behav. Ecol. Sociobiol."},{"issue":"22","key":"335_CR42","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1016\/j.cub.2008.09.064","volume":"18","author":"DJ Sumpter","year":"2008","unstructured":"Sumpter, D.J., Krause, J., James, R., Couzin, I.D., Ward, A.J.: Consensus decision making by fish. Curr. Biol. 18(22), 1773\u20131777 (2008)","journal-title":"Curr. Biol."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0335-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-018-0335-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0335-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T07:59:13Z","timestamp":1579161553000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-018-0335-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,6]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["335"],"URL":"https:\/\/doi.org\/10.1007\/s00446-018-0335-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2018,6,6]]},"assertion":[{"value":"29 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}