{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T23:58:50Z","timestamp":1773187130534,"version":"3.50.1"},"reference-count":18,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2012,5,28]],"date-time":"2012-05-28T00:00:00Z","timestamp":1338163200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well\u2010studied <jats:italic>push model<\/jats:italic>. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree <jats:italic>d<\/jats:italic> \u2265 3, i.e., the underlying graph is drawn uniformly at random from the set of all <jats:italic>d<\/jats:italic> \u2010regular graphs with <jats:italic>n<\/jats:italic> vertices. We show that with probability 1 \u2010 <jats:italic>o<\/jats:italic>(1) the push model broadcasts the message to all nodes within (1 + <jats:italic>o<\/jats:italic>(1))<jats:italic>C<\/jats:italic><jats:sub><jats:italic>d<\/jats:italic><\/jats:sub> ln<jats:italic>n<\/jats:italic> rounds, where\n<jats:disp-formula>\n\n<\/jats:disp-formula>\nParticularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo\u2010random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + <jats:italic>o<\/jats:italic>(1))<jats:italic>C<\/jats:italic>ln<jats:italic>n<\/jats:italic> with probability 1 \u2010 <jats:italic>o<\/jats:italic>(1), where\n<jats:styled-content>\\documentclass{article}\\usepackage{mathrsfs, amsmath, amssymb}\\pagestyle{empty}\\begin{document}\\begin{align*}C = \\lim_{d\\to\\infty}C_d = \\frac{1}{\\ln2} + 1\\end{align*} \\end{document}<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-ueqn-2.gif\" xlink:title=\"equation image\"\/><\/jats:styled-content>. \u00a9 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013<\/jats:p>","DOI":"10.1002\/rsa.20432","type":"journal-article","created":{"date-parts":[[2012,5,28]],"date-time":"2012-05-28T10:59:37Z","timestamp":1338202777000},"page":"201-220","source":"Crossref","is-referenced-by-count":17,"title":["Rumor spreading on random regular graphs and expanders"],"prefix":"10.1002","volume":"43","author":[{"given":"Nikolaos","family":"Fountoulakis","sequence":"first","affiliation":[]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2012,5,28]]},"reference":[{"key":"e_1_2_7_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"e_1_2_7_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_2_7_4_2","doi-asserted-by":"crossref","unstructured":"M.Bradonjic R.Els\u00e4sser T.Friedrich T.Sauerwald A.Stauffer Efficient broadcast on random geometric graphs In Proceedings of the 21st Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '10) Austin Texas U.S.A. 2010 pp.1412\u20131421.","DOI":"10.1137\/1.9781611973075.114"},{"key":"e_1_2_7_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125347"},{"key":"e_1_2_7_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_7_7_2","doi-asserted-by":"crossref","unstructured":"R.Els\u00e4sser T.Sauerwald On Broadcasting vs. mixing and information dissemination on Caley graphs In Proceedings of the 24th Symposium on Theoretical Aspects of Computing (STACS '07) Aachen Germany 2007 pp.163\u2013174.","DOI":"10.1007\/978-3-540-70918-3_15"},{"key":"e_1_2_7_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_7_9_2","doi-asserted-by":"crossref","unstructured":"N.Fountoulakis A.Huber K.Panagiotou Reliable broadcasting and the effect of density In Proceedings of INFOCOM '10 2010 pp.2552\u20132560.","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"e_1_2_7_10_2","first-page":"viii+100","article-title":"A proof of Alon's second eigenvalue conjecture and related problems","volume":"195","author":"Friedman J.","year":"2008","journal-title":"Mem Am Math Soc"},{"key":"e_1_2_7_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"e_1_2_7_12_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_7_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_7_14_2","first-page":"199","volume-title":"In Proceedings of the Conference on Finite and Infinite Sets, Bolyai Society Mathematical Studies 15","author":"Krivelevich M.","year":"2006"},{"key":"e_1_2_7_15_2","first-page":"353","volume-title":"In Combinatorics, Paul Erd\u0151s is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc Math Stud, 2, J\u00e1nos Bolyai Math Soc","author":"Lov\u00e1sz L.","year":"1996"},{"key":"e_1_2_7_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005089"},{"key":"e_1_2_7_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90112-F"},{"key":"e_1_2_7_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02699376"},{"key":"e_1_2_7_19_2","doi-asserted-by":"crossref","unstructured":"A.Thomason Pseudo\u2010random graphs In Proceedings of Random Graphs M.Karonski(Editor) 1987 pp.307\u2013331.","DOI":"10.1016\/S0304-0208(08)73063-9"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20432","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20432","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T21:23:09Z","timestamp":1698528189000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,28]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1002\/rsa.20432"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20432","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,28]]}}}