{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T06:51:44Z","timestamp":1780642304323,"version":"3.54.1"},"reference-count":101,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T00:00:00Z","timestamp":1583971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2020,3,12]]},"abstract":"<jats:p>The term distributed system typically refers to a set of entities, called nodes, connected by point-topoint communication links. The set of nodes together with the set of links form a network, which is usually represented by a graph. The term ?system\" is used to reflect the fact that nodes evolve over time, i.e., they change their internal states according to some local interaction-rule, which is applied in every time step (i.e. round).<\/jats:p>","DOI":"10.1145\/3388392.3388403","type":"journal-article","created":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T22:34:37Z","timestamp":1584052477000},"page":"58-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Consensus Dynamics"],"prefix":"10.1145","volume":"51","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[{"name":"Sapienza Universita di Roma, Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Clementi","sequence":"additional","affiliation":[{"name":"Universita Tor Vergata di Roma, Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emanuele","family":"Natale","sequence":"additional","affiliation":[{"name":"Universite Cote d'Azur, CNRS, INRIA, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,3,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0059-z"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039855"},{"key":"e_1_2_1_3_1","volume-title":"Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4):13","author":"Angluin D.","year":"2008","unstructured":"[AAFJ08] D. Angluin , J. Aspnes , M. J. Fischer , and H. Jiang . Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4):13 , 2008 . [AAFJ08] D. Angluin, J. Aspnes, M. J. Fischer, and H. Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4):13, 2008."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175449"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2490670"},{"issue":"1","key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","article-title":"Explicit construction of linear sized tolerant networks","volume":"72","author":"Alon N.","year":"1988","unstructured":"[AC88] N. Alon and F.R.K. Chung . Explicit construction of linear sized tolerant networks . Discrete Mathematics , 72 ( 1 ): 15 -- 19 , 1988 . [AC88] N. Alon and F.R.K. Chung. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 72(1):15 -- 19, 1988.","journal-title":"Discrete Mathematics"},{"key":"e_1_2_1_7_1","volume-title":"Reversible markov chains and random walks on graphs","author":"Aldous David","year":"1995","unstructured":"[AF95] David Aldous and James Fill . Reversible markov chains and random walks on graphs , 1995 . [AF95] David Aldous and James Fill. Reversible markov chains and random walks on graphs, 1995."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776178_3"},{"key":"e_1_2_1_9_1","series-title":"ICALP'15","first-page":"479","volume-title":"Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming","author":"Alistarh D.","year":"2015","unstructured":"[AG15] D. Alistarh and R. Gelashvili . Polylogarithmic-time leader election in population protocols . In Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming , volume 9135 of ICALP'15 , pages 479 -- 491 . Springer- Verlag New York, Inc. , 2015 . [AG15] D. Alistarh and R. Gelashvili. Polylogarithmic-time leader election in population protocols. In Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming, volume 9135 of ICALP'15, pages 479--491. Springer- Verlag New York, Inc., 2015."},{"key":"e_1_2_1_10_1","volume-title":"Milan Vojnovic. Fast and Exact Majority in Population Protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15","author":"Alistarh Dan","year":"2015","unstructured":"[AGV15] Dan Alistarh , Rati Gelashvili , and Milan Vojnovic. Fast and Exact Majority in Population Protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15 , New York, NY, USA , 2015 . ACM. [AGV15] Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and Exact Majority in Population Protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15, New York, NY, USA, 2015. ACM."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.3150\/12-BEJSP04"},{"key":"e_1_2_1_12_1","first-page":"98","article-title":"An introduction to population protocols","volume":"93","author":"Aspnes J.","year":"2007","unstructured":"[AR07] J. Aspnes and E. Ruppert . An introduction to population protocols . Bulletin of the EATCS , 93 : 98 -- 117 , 2007 . [AR07] J. Aspnes and E. Ruppert. An introduction to population protocols. Bulletin of the EATCS, 93:98--117, 2007.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed computing: fundamentals, simulations, and advanced topics","author":"Attiya Hagit","year":"2004","unstructured":"[AW04] Hagit Attiya and Jennifer Welch . Distributed computing: fundamentals, simulations, and advanced topics , volume 19 . John Wiley & Sons , 2004 . [AW04] Hagit Attiya and Jennifer Welch. Distributed computing: fundamentals, simulations, and advanced topics, volume 19. John Wiley & Sons, 2004."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.09.016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087817"},{"key":"e_1_2_1_16_1","volume-title":"26th Annual European Symposium on Algorithms, ESA 2018","author":"Becchetti Luca","year":"2018","unstructured":"[BCM+18] Luca Becchetti , Andrea E. F. Clementi , Pasin Manurangsi , Emanuele Natale , Francesco Pasquale , Prasad Raghavendra , and Luca Trevisan . Average whenever you meet: Opportunistic protocols for community detection . In 26th Annual European Symposium on Algorithms, ESA 2018 , August 20 --22 , 2018 , Helsinki, Finland, pages 7:1--7:13, 2018. [BCM+18] Luca Becchetti, Andrea E. F. Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan. Average whenever you meet: Opportunistic protocols for community detection. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20--22, 2018, Helsinki, Finland, pages 7:1--7:13, 2018."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.27"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch46"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0289-4"},{"key":"e_1_2_1_20_1","first-page":"940","volume-title":"Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17)","author":"Becchetti L.","year":"2017","unstructured":"[BCN+17b] L. Becchetti , A. Clementi , E. Natale , F. Pasquale , and L. Trevisan . Find your place: Simple distributed algorithms for community detection . In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17) , pages 940 -- 959 . Society for Industrial and Applied Mathematics , 2017 . [BCN+17b] L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Find your place: Simple distributed algorithms for community detection. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pages 940-- 959. Society for Industrial and Applied Mathematics, 2017."},{"key":"e_1_2_1_21_1","volume-title":"Friend or foe? population protocols can perform community detection. arXiv preprint arXiv:1703.05045","author":"Becchetti Luca","year":"2017","unstructured":"[BCN+17c] Luca Becchetti , Andrea Clementi , Emanuele Natale , Francesco Pasquale , Prasad Raghavendra , and Luca Trevisan . Friend or foe? population protocols can perform community detection. arXiv preprint arXiv:1703.05045 , 2017 . [BCN+17c] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan. Friend or foe? population protocols can perform community detection. arXiv preprint arXiv:1703.05045, 2017."},{"key":"e_1_2_1_22_1","article-title":"Randomized gossip algorithms","author":"Boyd S.","year":"2006","unstructured":"[BGPS06] S. Boyd , A. Ghosh , B. Prabhakar , and D. Shah . Randomized gossip algorithms . IEEE Transactions on Information Theory, pages 2508--2530 , 2006 . [BGPS06] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, pages 2508--2530, 2006.","journal-title":"IEEE Transactions on Information Theory, pages 2508--2530"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2009.4960420"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2011.2114326"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20586"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep00656"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933107"},{"key":"e_1_2_1_28_1","series-title":"LNCS","first-page":"435","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14)","author":"Cooper C.","year":"2014","unstructured":"[CER14] C. Cooper , R. Elsasser , and T. Radzik . The power of two choices in distributed voting . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14) , volume 8573 of LNCS , pages 435 -- 446 . Springer , 2014 . [CER14] C. Cooper, R. Elsasser, and T. Radzik. The power of two choices in distributed voting. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), volume 8573 of LNCS, pages 435--446. Springer, 2014."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48653-5_17"},{"key":"e_1_2_1_30_1","volume-title":"A tight analysis of the parallel undecided-state dynamics with two colors. CoRR, abs\/1707.05135","author":"Clementi A","year":"2017","unstructured":"[CGG+17] A Clementi , M. Ghaffari , L. Gual\u00e0 , F. Natale , E. Pasquale , and G. Scornavacca . A tight analysis of the parallel undecided-state dynamics with two colors. CoRR, abs\/1707.05135 , 2017 . [CGG+17] A Clementi, M. Ghaffari, L. Gual\u00e0, F. Natale, E. Pasquale, and G. Scornavacca. A tight analysis of the parallel undecided-state dynamics with two colors. CoRR, abs\/1707.05135, 2017."},{"key":"e_1_2_1_31_1","volume-title":"31st International Symposium on Distributed Computing, DISC 2017","author":"Clementi A.","year":"2017","unstructured":"[CGPS17] A. Clementi , L. Gual\u00e0 , F. Pasquale , and G. Scornavacca . Brief announcement: On the parallel undecided-state dynamics with two colors . In 31st International Symposium on Distributed Computing, DISC 2017 , October 16 --20 , 2017 , Vienna, Austria, pages 47:1--47:4, 2017. [CGPS17] A. Clementi, L. Gual\u00e0, F. Pasquale, and G. Scornavacca. Brief announcement: On the parallel undecided-state dynamics with two colors. In 31st International Symposium on Distributed Computing, DISC 2017, October 16--20, 2017, Vienna, Austria, pages 47:1--47:4, 2017."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380656.2380679"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.026"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.72"},{"key":"e_1_2_1_35_1","first-page":"67","volume-title":"Chemical Reaction Network Designs for Asynchronous Logic Circuits","author":"Cardelli L.","year":"2016","unstructured":"[CKW16] L. Cardelli , M. Z. Kwiatkowska , and M. Whitby . Chemical Reaction Network Designs for Asynchronous Logic Circuits , pages 67 -- 81 . Springer , 2016 . [CKW16] L. Cardelli, M. Z. Kwiatkowska, and M. Whitby. Chemical Reaction Network Designs for Asynchronous Logic Circuits, pages 67--81. Springer, 2016."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.001"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237499"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33016046"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"e_1_2_1_41_1","volume-title":"DISC","author":"Cooper Colin S","year":"2017","unstructured":"[CRRS17] Colin S Cooper , Tomasz Radzik , Nicol\u00e1s Rivera , and Takeharu Shiraga . Fast plurality consensus in regular expanders . In DISC , 2017 . [CRRS17] Colin S Cooper, Tomasz Radzik, Nicol\u00e1s Rivera, and Takeharu Shiraga. Fast plurality consensus in regular expanders. In DISC, 2017."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88869-7_27"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612712"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1974.10480137"},{"key":"e_1_2_1_45_1","volume-title":"Exact size counting in uniform population protocols in nearly logarithmic time. arXiv preprint arXiv:1805.04832","author":"Doty David","year":"2018","unstructured":"[DEM+18] David Doty , Mahsa Eftekhari , Othon Michail , Paul G Spirakis , and Michail Theofilatos . Exact size counting in uniform population protocols in nearly logarithmic time. arXiv preprint arXiv:1805.04832 , 2018 . [DEM+18] David Doty, Mahsa Eftekhari, Othon Michail, Paul G Spirakis, and Michail Theofilatos. Exact size counting in uniform population protocols in nearly logarithmic time. arXiv preprint arXiv:1805.04832, 2018."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989516"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75142-7_17"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.05.005"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"[Dol00] Shlomi Dolev. Self-Stabilization. MIT Press 2000.  [Dol00] Shlomi Dolev. Self-Stabilization. MIT Press 2000.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.57"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/110823018"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087860"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611469"},{"key":"e_1_2_1_58_1","first-page":"1","volume-title":"Distributed Computing","author":"Feinerman O.","year":"2015","unstructured":"[FHK15] O. Feinerman , B. Haeupler , and A. Korman . Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication . Distributed Computing , pages 1 -- 17 , 2015 . [FHK15] O. Feinerman, B. Haeupler, and A. Korman. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. Distributed Computing, pages 1--17, 2015."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1990.9990069"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36071-8_1"},{"key":"e_1_2_1_61_1","volume-title":"Towards a complexity theory for local distributed computing. Journal of the ACM (JACM), 60(5):35","author":"Fraigniaud Pierre","year":"2013","unstructured":"[FKP13] Pierre Fraigniaud , Amos Korman , and David Peleg . Towards a complexity theory for local distributed computing. Journal of the ACM (JACM), 60(5):35 , 2013 . [FKP13] Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. Journal of the ACM (JACM), 60(5):35, 2013."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933089"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstb.2002.1066"},{"key":"e_1_2_1_64_1","first-page":"57","volume-title":"Symposium on Theoretical Aspects of Computer Science (STACS'11)","author":"Giakkoupis G.","year":"2016","unstructured":"[Gia16] G. Giakkoupis . Tight bounds for rumor spreading in graphs of a given conductance . In Symposium on Theoretical Aspects of Computer Science (STACS'11) , LNCS, pages 57 -- 68 ,. Springer , 2016 . [Gia16] G. Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In Symposium on Theoretical Aspects of Computer Science (STACS'11), LNCS, pages 57--68,. Springer, 2016."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212738"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10614-005-6296-3"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3088"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00133-9"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-011-1157-0"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1312486110"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.59"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323207"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511780516"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892324"},{"key":"e_1_2_1_76_1","volume-title":"Paul erdos is eighty, 2(1):1--46","author":"L\u00e1szl\u00f3 Lov\u00e1sz","year":"1993","unstructured":"[L+93] L\u00e1szl\u00f3 Lov\u00e1sz et al. Random walks on graphs: A survey. Combinatorics , Paul erdos is eighty, 2(1):1--46 , 1993 . [L+93] L\u00e1szl\u00f3 Lov\u00e1sz et al. Random walks on graphs: A survey. Combinatorics, Paul erdos is eighty, 2(1):1--46, 1993."},{"key":"e_1_2_1_77_1","volume-title":"Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):37","author":"Lee James R","year":"2014","unstructured":"[LGT14] James R Lee , Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):37 , 2014 . [LGT14] James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):37, 2014."},{"key":"e_1_2_1_78_1","volume-title":"Interacting particle systems","author":"Liggett T.","year":"2012","unstructured":"[Lig12] T. Liggett . Interacting particle systems , volume 276 . Springer , 2012 . [Lig12] T. Liggett. Interacting particle systems, volume 276. Springer, 2012."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2009.12.019"},{"key":"e_1_2_1_80_1","volume-title":"Markov chains and mixing times","author":"Levin D. A.","year":"2009","unstructured":"[LPW09] D. A. Levin , Y. Peres , and E. L. Wilmer . Markov chains and mixing times . American Mathematical Society , 2009 . [LPW09] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2009."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"e_1_2_1_82_1","first-page":"871","volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I","author":"Mertzios George B.","year":"2014","unstructured":"[MNRS14] George B. Mertzios , Sotiris E. Nikoletseas , Christoforos Raptopoulos , and Paul G. Spirakis . Determining majority in networks with local interactions and very small local memory. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I , pages 871 -- 882 , 2014 . [MNRS14] George B. Mertzios, Sotiris E. Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. Determining majority in networks with local interactions and very small local memory. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I, pages 871-- 882, 2014."},{"key":"e_1_2_1_83_1","volume-title":"Distributed Computing (Ext.Abs. in ICALP'14)","author":"Mertzios George","year":"2016","unstructured":"[MNRS16] George Mertzios , Sotiris Nikoletseas , Christoforos Raptopoulos , and Paul Spirakis . Determining majority in networks with local interactions and very small local memory . Distributed Computing (Ext.Abs. in ICALP'14) , 30, 07 2016 . [MNRS16] George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis. Determining majority in networks with local interactions and very small local memory. Distributed Computing (Ext.Abs. in ICALP'14), 30, 07 2016."},{"key":"e_1_2_1_84_1","volume-title":"Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3--4):431--461","author":"Mossel E.","year":"2014","unstructured":"[MNS14] E. Mossel , J. Neeman , and A. Sly . Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3--4):431--461 , 2014 . [MNS14] E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3--4):431--461, 2014."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-013-9230-4"},{"key":"e_1_2_1_86_1","first-page":"214","volume-title":"Proceedings of the 2nd Innovations in Computer Science (ITCS'10)","author":"Mossel E.","year":"2010","unstructured":"[MS10] E. Mossel and G. Schoenebeck . Reaching consensus on social networks . In Proceedings of the 2nd Innovations in Computer Science (ITCS'10) , pages 214 -- 229 , 2010 . [MS10] E. Mossel and G. Schoenebeck. Reaching consensus on social networks. In Proceedings of the 2nd Innovations in Computer Science (ITCS'10), pages 214--229, 2010."},{"key":"e_1_2_1_87_1","volume-title":"Eigenvector computation and community detection in asynchronous gossip models. arXiv preprint arXiv:1804.08548","author":"Mallmann-Trenn Frederik","year":"2018","unstructured":"[MTMM18] Frederik Mallmann-Trenn , Cameron Musco , and Christopher Musco . Eigenvector computation and community detection in asynchronous gossip models. arXiv preprint arXiv:1804.08548 , 2018 . [MTMM18] Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. Eigenvector computation and community detection in asynchronous gossip models. arXiv preprint arXiv:1804.08548, 2018."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/2678280"},{"key":"e_1_2_1_89_1","volume-title":"Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15(3):267--273","author":"Oja Erkki","year":"1982","unstructured":"[Oja82] Erkki Oja . Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15(3):267--273 , 1982 . [Oja82] Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15(3):267--273, 1982."},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1137\/060678324"},{"key":"e_1_2_1_91_1","series-title":"SIAM Monographs on discrete mathematics and applications, 5","volume-title":"Distributed computing","author":"Peleg D.","year":"2000","unstructured":"[Pel00] D. Peleg . Distributed computing . SIAM Monographs on discrete mathematics and applications, 5 , 2000 . [Pel00] D. Peleg. Distributed computing. SIAM Monographs on discrete mathematics and applications, 5, 2000."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_2_1_94_1","first-page":"299","volume-title":"Molecular Computing","author":"Reus B.","year":"2016","unstructured":"[Reu16] B. Reus . Molecular Computing , pages 299 -- 316 . Springer , 2016 . [Reu16] B. Reus. Molecular Computing, pages 299--316. Springer, 2016."},{"key":"e_1_2_1_95_1","volume-title":"CIAC'19 - 11th International Conference on Algorithms and Complexity","author":"Ramezani Iliad","year":"2019","unstructured":"[RN19] Iliad Ramezani and Emanuele Natale . On the Necessary Memory to Compute the Plurality in Multi-Agent Systems . In CIAC'19 - 11th International Conference on Algorithms and Complexity , Rome, Italy , May 2019 . [RN19] Iliad Ramezani and Emanuele Natale. On the Necessary Memory to Compute the Plurality in Multi-Agent Systems. In CIAC'19 - 11th International Conference on Algorithms and Complexity, Rome, Italy, May 2019."},{"key":"e_1_2_1_96_1","volume-title":"Gossip algorithms","author":"Shah D.","year":"2009","unstructured":"[Sha09] D. Shah . Gossip algorithms . Now Publishers Inc , 2009 . [Sha09] D. Shah. Gossip algorithms. Now Publishers Inc, 2009."},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSIPN.2015.2477777"},{"key":"e_1_2_1_98_1","volume-title":"User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389--434","author":"Tropp Joel A","year":"2012","unstructured":"[Tro12] Joel A Tropp . User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389--434 , 2012 . [Tro12] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389--434, 2012."},{"key":"e_1_2_1_99_1","first-page":"433","volume-title":"Combinatorics: Paul Erd\u00f3s Is Eighty","author":"Winkler P.","year":"1993","unstructured":"[TW93] Tetali, P. and Winkler , P . Simultaneous reversible Markov chains . In Combinatorics: Paul Erd\u00f3s Is Eighty ,, volume Vol. 1 , pages 433 -- 451 , Budapest, 1993 . J\u00e1nos Bolyai Mathematical Society - D. Mikl\u00f3s , V. T. S\u00f3s, and T. Sz\u00f3nyi, Eds. [TW93] Tetali, P. and Winkler, P. Simultaneous reversible Markov chains. In Combinatorics: Paul Erd\u00f3s Is Eighty,, volume Vol. 1, pages 433--451, Budapest, 1993. J\u00e1nos Bolyai Mathematical Society - D. Mikl\u00f3s, V. T. S\u00f3s, and T. Sz\u00f3nyi, Eds."},{"key":"e_1_2_1_100_1","volume-title":"A New Kind of Science","author":"Wolfram S.","year":"2002","unstructured":"[Wol02] S. Wolfram . A New Kind of Science , volume 5 . Wolfram media Champaign , 2002 . [Wol02] S. Wolfram. A New Kind of Science, volume 5. Wolfram media Champaign, 2002."},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.08.010"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3388392.3388403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3388392.3388403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:20Z","timestamp":1750197680000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3388392.3388403"}},"subtitle":["An Overview"],"short-title":[],"issued":{"date-parts":[[2020,3,12]]},"references-count":101,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,12]]}},"alternative-id":["10.1145\/3388392.3388403"],"URL":"https:\/\/doi.org\/10.1145\/3388392.3388403","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2020,3,12]]},"assertion":[{"value":"2020-03-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}