{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:22Z","timestamp":1750308802579,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,11,16]],"date-time":"2008-11-16T00:00:00Z","timestamp":1226793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>We empirically analyze two versions of the well-known \u201crandomized rumor spreading\u201d protocol to disseminate a piece of information in networks. In the classical model, in each round, each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list.<\/jats:p>\n          <jats:p>While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model.<\/jats:p>\n          <jats:p>In this work, we compare the two models experimentally. Not only does this show that the quasirandom model generally is faster, but it also shows that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom process.<\/jats:p>\n          <jats:p>These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.<\/jats:p>","DOI":"10.1145\/1963190.2025379","type":"journal-article","created":{"date-parts":[[2012,10,15]],"date-time":"2012-10-15T19:22:23Z","timestamp":1350328943000},"source":"Crossref","is-referenced-by-count":30,"title":["Quasirandom rumor spreading"],"prefix":"10.1145","volume":"16","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Germany"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Germany"}]},{"given":"Marvin","family":"K\u00fcnnemann","sequence":"additional","affiliation":[{"name":"Universit\u00e4t des Saarlandes, Germany"}]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Germany"}]}],"member":"320","published-online":{"date-parts":[[2008,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s B. and Kohayakawa Y. 1997. On Richardson's model on the hypercube. In Combinatorics Geometry and Probability B. Bollob\u00e1s and A. Thomason Eds. Cambridge University Press Cambridge UK 129--137.  Bollob\u00e1s B. and Kohayakawa Y. 1997. On Richardson's model on the hypercube. In Combinatorics Geometry and Probability B. Bollob\u00e1s and A. Thomason Eds. Cambridge University Press Cambridge UK 129--137.","DOI":"10.1017\/CBO9780511662034.015"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103428478"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<183::AID-NET3>3.0.CO;2-E"},{"volume-title":"Proceedings of the 19th ACM SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Doerr B.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_31"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_36"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erd\u0151s P.","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005440"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/09075768X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v45:4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek J. 1999. Geometric Discrepancy. Springer-Verlag Berlin.  Matou\u0161ek J. 1999. Geometric Discrepancy. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-03942-3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Niederreiter H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics (SIAM) Philadelphia PA.   Niederreiter H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics (SIAM) Philadelphia PA.","DOI":"10.1137\/1.9781611970081"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003867"},{"key":"e_1_2_1_18_1","first-page":"239","article-title":"Models of random regular graphs","volume":"267","author":"Wormald N. C.","year":"1999","journal-title":"Surv. Comb."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.2025379","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1963190.2025379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:02Z","timestamp":1750278362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.2025379"}},"subtitle":["An experimental analysis"],"short-title":[],"issued":{"date-parts":[[2008,11,16]]},"references-count":18,"alternative-id":["10.1145\/1963190.2025379"],"URL":"https:\/\/doi.org\/10.1145\/1963190.2025379","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,11,16]]}}}