{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T04:40:03Z","timestamp":1746074403184,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_40","type":"book-chapter","created":{"date-parts":[[2013,12,12]],"date-time":"2013-12-12T02:32:52Z","timestamp":1386815572000},"page":"424-434","source":"Crossref","is-referenced-by-count":3,"title":["Asynchronous Rumor Spreading on Random Graphs"],"prefix":"10.1007","author":[{"given":"Konstantinos","family":"Panagiotou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leo","family":"Speidel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Aigner, M., Ziegler, G.: Proofs from THE BOOK. Springer (2010)","DOI":"10.1007\/978-3-642-00856-6"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A., Albert, R.: Emergence of scaling in random networks. Science\u00a0286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Boyd, S., Arpita, G., Balaji, P., Devavrat, S.: Gossip algorithms: Design, analysis and applications. In: 24th INFOCOM, pp. 1653\u20131664. IEEE (2005)","DOI":"10.1109\/INFCOM.2005.1498447"},{"issue":"6","key":"40_CR4","doi-asserted-by":"publisher","first-page":"2508","DOI":"10.1109\/TIT.2006.874516","volume":"52","author":"S. Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Transactions on Information Theory\u00a052(6), 2508\u20132530 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds for rumour spreading with conductance. In: 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 399\u2013408 (2010)","DOI":"10.1145\/1806689.1806745"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumour spreading and graph conductance. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 1657\u20131663 (2010)","DOI":"10.1137\/1.9781611973075.135"},{"issue":"1","key":"40_CR7","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1080\/15427951.2004.10129081","volume":"1","author":"F. Chung","year":"2003","unstructured":"Chung, F., Lu, L.: The average distance in a random graph with given expected degrees. Internet Mathematics\u00a01(1), 91\u2013114 (2003)","journal-title":"Internet Mathematics"},{"issue":"1-2","key":"40_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20151","volume":"30","author":"C. Cooper","year":"2007","unstructured":"Cooper, C., Frieze, A.: The cover time of sparse random graphs. Random Structures and Algorithms\u00a030(1-2), 1\u201316 (2007)","journal-title":"Random Structures and Algorithms"},{"key":"40_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 Sixth Annual ACM Symposium on Principles of Distributed Computing (POCD 1987), pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"key":"40_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. In: 43rd ACM Symposium on Theory of Computing, pp. 21\u201330 (2011)","DOI":"10.1145\/1993636.1993640"},{"key":"40_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-31155-0_27","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"B. Doerr","year":"2012","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Asynchronous rumor spreading in preferential attachment graphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 307\u2013315. Springer, Heidelberg (2012)"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Huber, A., Panagiotou, K.: Reliable broadcasting in random networks and the effect of density. In: 29th Conference on Computer Communications (IEEE INFOCOM 2010), pp. 2552\u20132560 (2010)","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1642\u20131660 (2012)","DOI":"10.1137\/1.9781611973099.130"},{"issue":"1","key":"40_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A.M. Frieze","year":"1985","unstructured":"Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics\u00a010(1), 57\u201377 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"40_CR15","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 57\u201368 (2011)"},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.M., van Steen, M.: Gossip-based peer sampling. ACM Transactions on Computer Systems\u00a025(3) (2007)","DOI":"10.1145\/1275517.1275520"},{"key":"40_CR17","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., V\u00f6cking, B.: Randomized rumor spreading. In: 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 565\u2013574 (2000)"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Klenke, A.: Probability theory: a comprehensive course. Springer (2008)","DOI":"10.1007\/978-1-84800-048-3"},{"key":"40_CR19","unstructured":"Massart, P.: Concentration Inequalities and Model Selection. Springer (2003)"},{"key":"40_CR20","unstructured":"Panagiotou, K., P\u00e9rez-Gim\u00e9nez, X., Sauerwald, T., Sun, H.: Randomized rumor spreading: the effect of the network topology (submitted)"},{"issue":"1","key":"40_CR21","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 Journal on Applied Mathematics\u00a047(1), 213\u2013223 (1987)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"Van Renesse, R., Minsky, Y., Hayden, M.: A gossip-style failure detection service. In: Middleware, pp. 55\u201370 (1998)","DOI":"10.1007\/978-1-4471-1283-9_4"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T04:24:48Z","timestamp":1746073488000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}