{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:26Z","timestamp":1740109286413,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,9,15]],"date-time":"2017-09-15T00:00:00Z","timestamp":1505433600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Austrian Science Fund (AT)","award":["P25214-N23"],"award-info":[{"award-number":["P25214-N23"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00446-017-0312-4","type":"journal-article","created":{"date-parts":[[2017,9,15]],"date-time":"2017-09-15T18:41:46Z","timestamp":1505500906000},"page":"503-513","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Breaking the $$\\log n$$ log n barrier on rumor spreading"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6647-8002","authenticated-orcid":false,"given":"Chen","family":"Avin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Els\u00e4sser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,15]]},"reference":[{"key":"312_CR1","doi-asserted-by":"crossref","unstructured":"Avin, C., Els\u00e4sser, R.: Faster rumor spreading: breaking the logn barrier. In: Proceedings of the 27th International Symposium on Distributed Computing\u2013DISC 2013, pp. 209\u2013223. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-41527-2_15"},{"key":"312_CR2","unstructured":"Avin, C., Lotker, Z., Pignolet, Y.-A., Turkel, I.: From caesar to twitter: structural properties of elites and rich-clubs. CoRR abs\/1111.3374 (2012)"},{"key":"312_CR3","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T.: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing , pp. 155\u2013164 (2008)","DOI":"10.1145\/1400751.1400773"},{"issue":"2","key":"312_CR4","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s00453-013-9861-5","volume":"72","author":"P Berenbrink","year":"2015","unstructured":"Berenbrink, P., Els\u00e4sser, R., Sauerwald, T.: Communication complexity of quasirandom rumor spreading. Algorithmica 72(2), 467\u2013492 (2015)","journal-title":"Algorithmica"},{"key":"312_CR5","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Haeupler, B., Kelner, J., Maymounkov, P.: Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In: Proceedings of the 44th ACM Symposium on Theory of Computing, pp. 961\u2013970 (2012)","DOI":"10.1145\/2213977.2214064"},{"key":"312_CR6","doi-asserted-by":"crossref","unstructured":"Chaintreau, A., Fraigniaud, P., Lebhar, E.: Opportunistic spatial gossip over mobile social networks. In: Proceedings of the 1st Workshop on Online Social Networks , pp. 73\u201378 (2008)","DOI":"10.1145\/1397735.1397752"},{"key":"312_CR7","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/PL00012580","volume":"6","author":"F Chung","year":"2002","unstructured":"Chung, F., Lu, L.: Connected components in random graphs with a given degree expected sequence. Ann. Comb. 6, 125\u2013145 (2002)","journal-title":"Ann. Comb."},{"issue":"6","key":"312_CR8","doi-asserted-by":"crossref","first-page":"2486","DOI":"10.1109\/TIT.2006.874532","volume":"52","author":"S Deb","year":"2006","unstructured":"Deb, S., M\u00e9dard, M., Choute, C.: Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE Trans. Inf. Theory 52(6), 2486\u20132507 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"312_CR9","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 , pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"key":"312_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. In: Proceeding of the 43rd Annual ACM Symposium on Theory of Computing , pp. 21\u201330 (2011)","DOI":"10.1145\/1993636.1993640"},{"key":"312_CR11","doi-asserted-by":"crossref","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 773\u2013781 (2008)","DOI":"10.1145\/1963190.2025379"},{"key":"312_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading: expanders, Push vs. Pull and Robustness. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 366\u2013377 (2009)","DOI":"10.1007\/978-3-642-02927-1_31"},{"key":"312_CR13","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. In: Proceedings of the 17th International Symposium on Algorithms and Computation, pp. 349\u2013358 (2006)","DOI":"10.1007\/11940128_36"},{"key":"312_CR14","unstructured":"Els\u00e4sser, R., Sauerwald, T.: The power of memory in randomized broadcasting. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 218\u2013227 (2008)"},{"issue":"4","key":"312_CR15","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447\u2013460 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"312_CR16","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1642\u20131660 (2012)","DOI":"10.1137\/1.9781611973099.130"},{"issue":"1","key":"312_CR17","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"AM Frieze","year":"1985","unstructured":"Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10(1), 57\u201377 (1985)","journal-title":"Discrete Appl. Math."},{"key":"312_CR18","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: 28th International Symposium on Theoretical Aspects of Computer Science, pp. 57\u201368 (2011)"},{"issue":"8","key":"312_CR19","doi-asserted-by":"crossref","first-page":"3830","DOI":"10.1137\/090769752","volume":"39","author":"M Gurevich","year":"2010","unstructured":"Gurevich, M., Keidar, I.: Correctness of gossip-based membership under message loss. SIAM J. Comput. 39(8), 3830\u20133859 (2010)","journal-title":"SIAM J. Comput."},{"key":"312_CR20","doi-asserted-by":"crossref","unstructured":"Haeupler, B.: Simple, fast and deterministic gossip and rumor spreading. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 705\u2013716 (2013)","DOI":"10.1137\/1.9781611973105.51"},{"key":"312_CR21","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Malkhi, D.: Optimal gossip with direct addressing. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, New York, NY, PODC \u201914, pp. 176\u2013185. ACM (2014)","DOI":"10.1145\/2611462.2611489"},{"key":"312_CR22","doi-asserted-by":"crossref","unstructured":"Harchol-Balter, M., Leighton, T., Lewin, D.: Resource discovery in distributed networks. In: Proceedings of the 18th Annual ACM symposium on Principles of Distributed Computing, pp. 229\u2013237 (1999)","DOI":"10.1145\/301308.301362"},{"key":"312_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., V\u00f6cking, B.: Randomized rumor spreading. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 565\u2013574 (2000)","DOI":"10.1109\/SFCS.2000.892324"},{"key":"312_CR24","doi-asserted-by":"crossref","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 482\u2013491 (2003)","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"312_CR25","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"issue":"1","key":"312_CR26","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/j.comnet.2006.02.005","volume":"51","author":"S Kutten","year":"2007","unstructured":"Kutten, S., Peleg, D.: Asynchronous resource discovery in peer-to-peer networks. Comput. Netw. 51(1), 190\u2013206 (2007)","journal-title":"Comput. Netw."},{"issue":"5","key":"312_CR27","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00224-003-1084-8","volume":"36","author":"S Kutten","year":"2003","unstructured":"Kutten, S., Peleg, D., Vishkin, U.: Deterministic resource discovery in distributed networks. Theory Comput. Syst. 36(5), 479\u2013495 (2003)","journal-title":"Theory Comput. Syst."},{"key":"312_CR28","volume-title":"Introduction to Parallel Algorithms and Architectures","author":"FT Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, San Francisco (1992)"},{"issue":"1","key":"312_CR29","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in o (log log n) communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"312_CR30","doi-asserted-by":"crossref","unstructured":"Mahlmann, P., Schindelhauer, C.: Distributed random digraph transformations for peer-to-peer networks. In: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 308\u2013317 (2006)","DOI":"10.1145\/1148109.1148162"},{"key":"312_CR31","doi-asserted-by":"crossref","unstructured":"Melamed, R., Keidar, I.: Araneola: a scalable reliable multicast system for dynamic environments. In: Proceedings Third IEEE International Symposium on Network Computing and Applications, 2004 (NCA 2004), pp. 5\u201314. IEEE (2004)","DOI":"10.1109\/NCA.2004.1347755"},{"key":"312_CR32","doi-asserted-by":"crossref","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, New York (2005)"},{"issue":"1","key":"312_CR33","doi-asserted-by":"crossref","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":"312_CR34","doi-asserted-by":"crossref","unstructured":"Raab, M., Steger, A.: \u201cBalls into bins\u201d\u2014a simple and tight analysis. In: Proceedings of the RANDOM\/APPROX. pp. 159\u2013170 (1998)","DOI":"10.1007\/3-540-49543-6_13"},{"issue":"1","key":"312_CR35","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s00453-008-9245-4","volume":"56","author":"T Sauerwald","year":"2010","unstructured":"Sauerwald, T.: On mixing and edge expansion properties in randomized broadcasting. Algorithmica 56(1), 51\u201388 (2010)","journal-title":"Algorithmica"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0312-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0312-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0312-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T23:12:53Z","timestamp":1693005173000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0312-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,15]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["312"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0312-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,9,15]]}}}