{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T11:49:58Z","timestamp":1759664998640,"version":"3.41.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T00:00:00Z","timestamp":1470009600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00453-016-0188-x","type":"journal-article","created":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T14:10:11Z","timestamp":1470060611000},"page":"968-989","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Asynchronous Rumor Spreading on Random Graphs"],"prefix":"10.1007","volume":"78","author":[{"given":"K.","family":"Panagiotou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4644-8033","authenticated-orcid":false,"given":"L.","family":"Speidel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,1]]},"reference":[{"key":"188_CR1","unstructured":"Acan, H., Collevecchio, A., Mehrabian, A., Wormald, N.: On the push and pull protocol for rumour spreading. arXiv:1411.0948"},{"key":"188_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-00856-6","volume-title":"Proofs from the Book","author":"M Aigner","year":"2010","unstructured":"Aigner, M., Ziegler, G.: Proofs from the Book. Springer, Berlin (2010)"},{"key":"188_CR3","doi-asserted-by":"crossref","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 286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"188_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs, Cambridge Studies in Advanced Mathematics","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, Cambridge Studies in Advanced Mathematics, vol. 73, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"188_CR5","volume-title":"On Richardsons Model on the Hypercube","author":"B Bollob\u00e1s","year":"1997","unstructured":"Bollob\u00e1s, B., Kohayakawa, Y.: On Richardsons Model on the Hypercube. Cambridge University Press, Cambridge (1997)"},{"key":"188_CR6","doi-asserted-by":"crossref","unstructured":"Boyd, S., Arpita, G., Balaji, P., Devavrat, S.: Gossip algorithms: Design, analysis and applications. In: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201905), pp. 1653\u20131664. Miami, FL, USA (2005)","DOI":"10.1109\/INFCOM.2005.1498447"},{"key":"188_CR7","doi-asserted-by":"crossref","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 Trans. Inf. Theory 52, 2508\u20132530 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"188_CR8","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds for rumour spreading with conductance. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC \u201910), pp. 399\u2013408. Cambridge, MA, USA (2010)","DOI":"10.1145\/1806689.1806745"},{"key":"188_CR9","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumour spreading and graph conductance. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910), pp. 1657\u20131663. Austin, TX, USA (2010)","DOI":"10.1137\/1.9781611973075.135"},{"key":"188_CR10","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","volume":"99","author":"F Chung","year":"2002","unstructured":"Chung, F., Lu, L.: The average distance in a random graph with given expected degrees. Proc Natl Acad Sci USA 99, 15879\u201315882 (2002)","journal-title":"Proc Natl Acad Sci USA"},{"key":"188_CR11","doi-asserted-by":"crossref","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 Struct. Algorithms 30, 1\u201316 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"188_CR12","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 (POCD\u201987), pp. 1\u201312. Vancouver, BC, Canada (1987)","DOI":"10.1145\/41840.41841"},{"key":"188_CR13","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.endm.2011.09.050","volume":"38","author":"B Doerr","year":"2011","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. Electron Notes Discret. Math. 38, 303\u2013308 (2011)","journal-title":"Electron Notes Discret. Math."},{"key":"188_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Asynchronous rumor spreading in preferential attachment graphs. In: Proceedings of the 13th Scandinavian Workshop on Algorithm Theory (SWAT\u201912), pp. 307\u2013315. Helsinki, Finland (2012)","DOI":"10.1007\/978-3-642-31155-0_27"},{"key":"188_CR15","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York, NY (1968)"},{"key":"188_CR16","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1214\/aoap\/1177005440","volume":"3","author":"JA Fill","year":"1993","unstructured":"Fill, J.A., Pemantle, R.: Percolation, first-passage percolation and covering times for Richardson\u2019s model on the $$n$$ n -cube. Ann. Appl. Probab. 3, 593\u2013629 (1993)","journal-title":"Ann. Appl. Probab."},{"key":"188_CR17","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Huber, A., Panagiotou, K.: Reliable broadcasting in random networks and the effect of density. In: Proceedings of the 29th Conference on Computer Communications (INFOCOM \u201910), pp. 2552\u20132560. San Diego, CA, USA (2010)","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"188_CR18","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 \u201912), pp. 1642\u20131660. Kyoto, Japan (2012)","DOI":"10.1137\/1.9781611973099.130"},{"key":"188_CR19","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A Frieze","year":"1985","unstructured":"Frieze, A., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10, 57\u201377 (1985)","journal-title":"Discrete Appl. Math."},{"key":"188_CR20","unstructured":"Giakkoupis, G.: 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\u201911), pp. 57\u201368. Dortmund, Germany (2011)"},{"key":"188_CR21","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1017\/S0963548399003892","volume":"8","author":"S Janson","year":"1999","unstructured":"Janson, S.: One, two and three times log n\/n for paths in a complete graph with random weights. Comb. Probab. Comput. 8, 347\u2013361 (1999)","journal-title":"Comb. Probab. Comput."},{"key":"188_CR22","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/1275517.1275520","volume":"25","author":"M Jelasity","year":"2007","unstructured":"Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.M., van Steen, M.: Gossip-based peer sampling. ACM Trans. Comput. Syst. 25, 8 (2007)","journal-title":"ACM Trans. Comput. Syst."},{"key":"188_CR23","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., V\u00f6cking, B.: Randomized rumor spreading. In: Proceedings of the 41th Annual Symposium on Foundations of Computer Science (FOCS\u201900), pp. 565\u2013574. Redondo Beach, CA, USA (2000)"},{"key":"188_CR24","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20432","volume":"43","author":"K Panagiotou","year":"2013","unstructured":"Panagiotou, K., Fountoulakis, N.: Rumor spreading on random regular graphs and expanders. Random Struct. Algorithms 43, 201\u2013220 (2013)","journal-title":"Random Struct. Algorithms"},{"key":"188_CR25","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1017\/S0963548314000194","volume":"24","author":"K Panagiotou","year":"2015","unstructured":"Panagiotou, K., P\u00e9rez-Gim\u00e9nez, X., Sauerwald, T., Sun, H.: Randomized rumour spreading: the effect of the network topology. Comb. Probab. Comput. 24, 457\u2013479 (2015)","journal-title":"Comb. Probab. Comput."},{"key":"188_CR26","doi-asserted-by":"crossref","unstructured":"Panagiotou, K., Speidel, L.: Asynchronous rumor spreading on random graphs. In: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC\u201913), pp. 424\u2013434. Hong Kong, China (2013)","DOI":"10.1007\/978-3-642-45030-3_40"},{"key":"188_CR27","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, 213\u2013223 (1987)","journal-title":"SIAM J. Appl. Math."},{"key":"188_CR28","doi-asserted-by":"crossref","unstructured":"van Renesse, R., Minsky, Y., Hayden, M.: A gossip-style failure detection service. In: Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware\u201998), pp. 55\u201370. The Lake District, UK (1998)","DOI":"10.1007\/978-1-4471-1283-9_4"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0188-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0188-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0188-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0188-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T10:37:40Z","timestamp":1749033460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0188-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0188-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,8,1]]}}}