Rumor spreading on random regular graphs and expanders12. Issue 2 (28th May 2012)

• Record Type: Journal Article
• Authors: Fountoulakis, Nikolaos; Panagiotou, Konstantinos
• Is Part Of: Random structures & algorithms. Volume 43:Issue 2(2013)
• Page Start: 201
• Page End: 220
• Publication Date: 2012-05-28
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20432
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well‐studied <italic>push model</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 <italic>d</italic> ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all <italic>d</italic> ‐regular graphs with <italic>n</italic> vertices. We show that with probability 1 ‐ <italic>o</italic>(1) the push model broadcasts the message to all nodes within (1 + <italic>o</italic>(1))<italic>C</italic><sub><italic>d</italic></sub> ln<italic>n</italic> rounds, where <disp-formula content-type="mathematics" id="di-ueqn-1"><alternatives><graphic position="anchor" mimetype="image" xlink:href="ark:/27927/pgg277vbthz" orientation="portrait" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*} C_d = \frac{1}{\ln\left(2\left(1-\frac{1}{d}\right)\right)} - \frac{1}{d\ln\left(1 - \frac{1}{d}\right)}.\end{align*}\end{document}]]></tex-math></alternatives></disp-formula> Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo‐random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + <italic>o</italic>(1))<italic>C</italic>ln<italic>n</italic> with probability 1 ‐ <italic>o</italic>(1), where <tex-math notation="LaTeX"><![CDATA[\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}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg277vbtd9" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>