{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:37:41Z","timestamp":1787510261762,"version":"build-2736575974"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T00:00:00Z","timestamp":1414627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001655","name":"German Academic Exchange Service","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,11,17]]},"abstract":"<jats:p>\n                    We propose and analyze a quasirandom analogue of the classical push model for disseminating information in networks (\u201crandomized rumor spreading\u201d). In the classical model, in each round, each informed vertex chooses a neighbor at random and informs it, if it was not informed before. It is known that this simple protocol succeeds in spreading a rumor from one vertex to all others within\n                    <jats:italic>O<\/jats:italic>\n                    (log\n                    <jats:italic>n<\/jats:italic>\n                    ) rounds on complete graphs, hypercubes, random regular graphs, Erd\u0151s-R\u00e9nyi random graphs, and Ramanujan graphs with probability 1 \u2212\n                    <jats:italic>o<\/jats:italic>\n                    (1). In the quasirandom model, we assume that each vertex has a (cyclic) list of its neighbors. Once informed, it starts at a random position on the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the above-mentioned bounds still hold. In some cases, even better bounds than for the classical model can be shown.\n                  <\/jats:p>","DOI":"10.1145\/2650185","type":"journal-article","created":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T15:28:54Z","timestamp":1414769334000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Quasirandom Rumor Spreading"],"prefix":"10.1145","volume":"11","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Universit\u00e4t Jena, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"University of Cambridge, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.37236\/191"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00015-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29952-0_34"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 18th European Symposium on Algorithms (ESA). 134--145","author":"Berenbrink P.","unstructured":"P. Berenbrink , R. Els\u00e4sser , and T. Sauerwald . 2010. Communication complexity of quasirandom rumor spreading . In Proceedings of the 18th European Symposium on Algorithms (ESA). 134--145 . P. Berenbrink, R. Els\u00e4sser, and T. Sauerwald. 2010. Communication complexity of quasirandom rumor spreading. In Proceedings of the 18th European Symposium on Algorithms (ESA). 134--145."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1009"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050406"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290805"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1657--1663","author":"Chierichetti F.","unstructured":"F. Chierichetti , S. Lattanzi , and A. Panconesi . 2010b. Rumour spreading and graph conductance . In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1657--1663 . F. Chierichetti, S. Lattanzi, and A. Panconesi. 2010b. Rumour spreading and graph conductance. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1657--1663."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007978"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332440"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:1\/2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v37:3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.018"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007565"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/43921.43922"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.11.006"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993640"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009589"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963190.2025379"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 773--781","author":"Doerr B.","unstructured":"B. Doerr , T. Friedrich , and T. Sauerwald . 2008. Quasirandom rumor spreading . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 773--781 . B. Doerr, T. Friedrich, and T. Sauerwald. 2008. Quasirandom rumor spreading. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 773--781."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_31"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.10.014"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.   D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102408341"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.017"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/09075768X"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 2552--2560","author":"Fountoulakis N.","unstructured":"N. Fountoulakis , A. Huber , and K. Panagiotou . 2010. Reliable broadcasting in random networks and the effect of density . In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 2552--2560 . N. Fountoulakis, A. Huber, and K. Panagiotou. 2010. Reliable broadcasting in random networks and the effect of density. In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 2552--2560."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM). 560--573","author":"Fountoulakis N.","unstructured":"N. Fountoulakis and K. Panagiotou . 2010. Rumor spreading on random regular graphs and expanders . In Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM). 560--573 . N. Fountoulakis and K. Panagiotou. 2010. Rumor spreading on random regular graphs and expanders. In Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM). 560--573."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1642--1660","author":"Fountoulakis N.","unstructured":"N. Fountoulakis , K. Panagiotou , and T. Sauerwald . 2012. Ultra-fast rumor spreading in social networks . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1642--1660 . N. Fountoulakis, K. Panagiotou, and T. Sauerwald. 2012. Ultra-fast rumor spreading in social networks. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1642--1660."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1620--1629","author":"Friedrich T.","unstructured":"T. Friedrich , M. Gairing , and T. Sauerwald . 2010. Quasirandom load balancing . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1620--1629 . T. Friedrich, M. Gairing, and T. Sauerwald. 2010. Quasirandom load balancing. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1620--1629."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.37236\/439"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS). 57--68","author":"Giakkoupis G.","year":"2011","unstructured":"G. Giakkoupis . 2011 . Tight bounds for rumor spreading in graphs of a given conductance . In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS). 57--68 . G. Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS). 57--68."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS). 314--325","author":"Giakkoupis G.","unstructured":"G. Giakkoupis , T. Sauerwald , H. Sun , and P. Woelfel . 2012. Low randomness rumor spreading via hashing . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS). 314--325 . G. Giakkoupis, T. Sauerwald, H. Sun, and P. Woelfel. 2012. Low randomness rumor spreading via hashing. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS). 314--325."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 449--461","author":"Giakkoupis G.","unstructured":"G. Giakkoupis and P. Woelfel . 2011. On the randomness requirements of rumor spreading . In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 449--461 . G. Giakkoupis and P. Woelfel. 2011. On the randomness requirements of rumor spreading. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 449--461."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180406"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210136"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS). 482--491","author":"Kempe D.","unstructured":"D. Kempe , A. Dobra , and J. Gehrke . 2003. Gossip-based computation of aggregate information . In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS). 482--491 . D. Kempe, A. Dobra, and J. Gehrke. 2003. Gossip-based computation of aggregate information. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS). 482--491."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02984814"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148162"},{"key":"e_1_2_1_49_1","volume-title":"Surveys in Combinatorics","author":"McDiarmid C.","year":"1989","unstructured":"C. McDiarmid . 1989. On the method of bounded differences . In Surveys in Combinatorics , 1989 (Norwich, 1989). London Mathematical Society Lecture Note Series, vol. 141 . Cambridge University Press , Cambridge, 148--188. C. McDiarmid. 1989. On the method of bounded differences. In Surveys in Combinatorics, 1989 (Norwich, 1989). London Mathematical Society Lecture Note Series, vol. 141. Cambridge University Press, Cambridge, 148--188."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146401"},{"key":"e_1_2_1_52_1","volume-title":"Random Number Generation and Quasi-Monte Carlo Methods","author":"Niederreiter H.","unstructured":"H. Niederreiter . 1992. Random Number Generation and Quasi-Monte Carlo Methods . SIAM , Philadelphia, PA . H. Niederreiter. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0147013"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.77.5079"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS). 694--705","author":"Rabani Y.","unstructured":"Y. Rabani , A. Sinclair , and R. Wanka . 1998. Local divergence of Markov chains and the analysis of iterative load balancing . In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS). 694--705 . Y. Rabani, A. Sinclair, and R. Wanka. 1998. Local divergence of Markov chains and the analysis of iterative load balancing. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS). 694--705."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9245-4"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS). 219--230","author":"Wagner I. A.","unstructured":"I. A. Wagner , M. Lindenbaum , and A. M. Bruckstein . 1996. Smell as a computational resource\u2014a lesson we can learn from the ant . In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS). 219--230 . I. A. Wagner, M. Lindenbaum, and A. M. Bruckstein. 1996. Smell as a computational resource\u2014a lesson we can learn from the ant. In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS). 219--230."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.795795"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650185","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2650185","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:54Z","timestamp":1750212714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650185"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,30]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2650185"],"URL":"https:\/\/doi.org\/10.1145\/2650185","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,30]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}