% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.23}{22(1)}{2015} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} \usepackage{amsmath, amssymb, amsthm, bbm, bm} % we recommend the graphicx package for importing figures %\usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{thm}{Theorem} %[chapter] \newtheorem{fact}[thm]{Fact} \newtheorem{lem}[thm]{Lemma} \newtheorem*{defi}{Definition} \newtheorem{obs}[thm]{Observation} \newtheorem{clm}[thm]{Claim} \newtheorem{cor}[thm]{Corollary} \newtheorem{fac}[thm]{Fact} \newtheorem{rem}[thm]{Remark} \newtheorem{ass}[thm]{Assumption} \newtheorem{pro}[thm]{Proposition} \newtheorem{con}[thm]{Conjecture} \numberwithin{thm}{section} \usepackage[active]{srcltx} \usepackage{tikz} \usepackage{hyperref} \usepackage{enumerate} \renewcommand{\leq}{\leqslant} \renewcommand{\geq}{\geqslant} \renewcommand{\le}{\leqslant} \renewcommand{\ge}{\geqslant} \renewcommand{\ln}{\log} %\renewcommand{\loge}{\ln} \newcommand{\thmref}[1]{Theorem~\ref{thm:#1}} \newcommand{\lemref}[1]{Lemma~\ref{lem:#1}} \newcommand{\clmref}[1]{Claim~\ref{lem:#1}} \newcommand{\corref}[1]{Corollary~\ref{cor:#1}} \newcommand{\defref}[1]{Definition~\ref{def:#1}} \newcommand{\figref}[1]{Figure~\ref{fig:#1}} \newcommand{\secref}[1]{Section~\ref{sec:#1}} \newcommand{\remref}[1]{Remark~\ref{rem:#1}} \newcommand{\Oh}{\mathcal{O}} \renewcommand{\Pr}[1]{\ensuremath{\operatorname{\mathbf{Pr}}\left[#1\right]}} \newcommand{\Prbig}[1]{\ensuremath{\operatorname{\mathbf{Pr}}\big[#1\big]}} \newcommand{\PrBig}[1]{\ensuremath{\operatorname{\mathbf{Pr}}\Big[#1\Big]}} \newcommand{\Pro}[1]{\ensuremath{\operatorname{\mathbf{Pr}}\left[#1\right]}} \newcommand{\Ex}[1]{\ensuremath{\operatorname{\mathbf{E}}\left[#1\right]}} \newcommand{\Var}[1]{\ensuremath{\operatorname{\mathbf{Var}}\left[#1\right]}} \newcommand{\Cov}[1]{\ensuremath{\operatorname{\mathbf{Cov}}\left[#1\right]}} \newcommand{\Exbig}[1]{\ensuremath{\operatorname{\mathbf{E}}\big[#1\big]}} \newcommand{\ExBig}[1]{\ensuremath{\operatorname{\mathbf{E}}\Big[#1\Big]}} \newcommand{\Exbigg}[1]{\ensuremath{\operatorname{\mathbf{E}}\bigg[#1\bigg]}} \newcommand{\ExBigg}[1]{\ensuremath{\operatorname{\mathbf{E}}\Bigg[#1\Bigg]}} %\usepackage{setspace,color} % just for \NOTE %\newcommand{\NOTE}[2]{$^{\textcolor{red}\clubsuit}$\marginpar{\setstretch{0.43}\textcolor{blue}{\bf\tiny #1: }\textcolor{red}{\bf\tiny #2}}} %\newcommand{\red}[1]{\textcolor{red}{#1}} %\renewcommand{\NOTE}[2]{#1} %\renewcommand{\red}[1]{#1} %\setlength{\marginparwidth}{1.5cm} % define \againlem, \againthm, \againpro \newcommand{\mylem}[2]{\begin{lem}\label{lem:#1}#2\end{lem}} \newcommand{\againlem}[2]{\noindent\textbf{Restatement of \lemref{#1}} (from page \pageref{lem:#1})\textbf{.}\emph{#2}\par} \newcommand{\mythm}[2]{\begin{thm}\label{thm:#1}#2\end{thm}} \newcommand{\againthm}[2]{\noindent\textbf{Restatement of \thmref{#1}} (from page \pageref{thm:#1})\textbf{.}\emph{#2}\par} \newcommand{\mycor}[2]{\begin{cor}\label{cor:#1}#2\end{cor}} \newcommand{\againcor}[2]{\noindent\textbf{Restatement of \corref{#1}} (from page \pageref{cor:#1})\textbf{.}\emph{#2}\par} \newcommand{\mypro}[2]{\begin{pro}\label{pro:#1}#2\end{pro}} \newcommand{\againpro}[2]{\noindent\textbf{Restatement of \proref{#1}} (from page \pageref{pro:#1})\textbf{.}\emph{#2}\par} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Faster rumor spreading with multiple calls} \author{Konstantinos Panagiotou\\ \small Ludwig-Maximilians-University\\[-0.8ex] \small Munich, Germany\\ \small\tt kpanagio@math.lmu.de\\ \and Ali Pourmiri\\ \small Max Planck Institute for Informatics\\[-0.8ex] \small Saarbr\"ucken, Germany\\ \small\tt pourmiri@mpi-inf.mpg.de\\ \and Thomas Sauerwald\\ \small University of Cambridge\\[-0.8ex] \small Cambridge, United Kingdom\\ \small\tt thomas.sauerwald@cl.cam.ac.uk} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Apr 25, 2014}{Dec 16, 2014}{Feb 9, 2015}\\ \small Mathematics Subject Classifications: 68W20; 68M14; 05C90} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We consider the random phone call model introduced by Demers et al.,%~\cite{DGH+87}, which is a well-studied model for information dissemination in networks. One basic protocol in this model is the so-called {\sf Push} protocol that proceeds in synchronous rounds. Starting with a single node which knows of a rumor, every informed node calls in each round a random neighbor and informs it of the rumor. The {\sf Push-Pull} protocol works similarly, but additionally every uninformed node calls a random neighbor and may learn the rumor from it. It is well-known that both protocols need $\Theta(\log n)$ rounds to spread a rumor on a complete network with $n$ nodes. Here we are interested in how much the spread can be speeded up by enabling nodes to make more than one call in each round. We propose a new model where the number of calls of a node is chosen independently according to a probability distribution $R$. We provide both lower and upper bounds on the rumor spreading time depending on statistical properties of $R$ such as the mean or the variance (if they exist). In particular, if $R$ follows a power law distribution with exponent $\beta \in (2,3)$, we show that the {\sf Push-Pull} protocol spreads a rumor in $\Theta(\log \log n)$ rounds. Moreover, when $\beta=3$, the {\sf Push-Pull} protocol spreads a rumor in $\Theta(\frac{ \log n}{\log\log n})$ rounds. \end{abstract} \newpage \tableofcontents \newpage \section{Introduction} Randomized rumor spreading is an important primitive for spreading information in networks. The goal is to spread a piece of information, the so-called {rumor}, from an arbitrary node to all the other nodes. Randomized rumor spreading protocols are based on the simple idea that every node picks a random neighbor and these two nodes are able to exchange information in that round. This paradigm ensures that the protocol is local, scalable, and robust against network failures (cf.~\cite{ES06,FPRU90}). Therefore, these protocols have been successfully applied in other contexts such as replicated databases~\cite{DGH+87}, failure detection~\cite{Renesse1998}, resource discovery~\cite{Harchol-Balter1999}, load balancing~\cite{Boyd2006}, data aggregation~\cite{KDG03}, and analysis of the spread of computer viruses~\cite{BBCS05}. The most basic variant of randomized rumor spreading is the {\sf Push} protocol. At the beginning, there is a single node who knows of some rumor. Then in each of the following rounds every \emph{informed} node calls a random neighbor chosen independently and uniformly at random and informs it of the rumor. The {\sf Pull} protocol is symmetric, here every \emph{uninformed} node calls a random neighbor chosen independently and uniformly at random, and if that neighbor happens to be informed the node becomes informed. The {\sf Push-Pull} protocol is simply the combination of both protocols. Most studies in randomized rumor spreading concern the \emph{runtime}, which is the number of rounds required until the rumor reaches all other nodes, and the \emph{communication overhead}, which is the total number of information exchanges, produced by these protocols (see e.g. \cite{KSSV00}). In one of the first papers in this area, Frieze and Grimmett~\cite{FG85} proved that if the underlying graph is a complete graph with $n$ nodes, then the runtime of {\sf Push} is $\log_2 n + \log n \pm o(\log n)$ with high probability\footnote{with probability $1-o(1)$ as $n \rightarrow \infty$. For simplicity, we sometimes omit the ``with high probability'' in the introduction.}, where $\log n$ denotes the natural logarithm of $n$. This result was later strengthened by Pittel~\cite{Pit87}. For the standard {\sf Push-Pull} protocol, Karp et al.~\cite{KSSV00} proved a runtime bound of $\log_3 n + \Oh(\log \log n)$. In order to overcome the large number of $\Theta(n \log n)$ calls, Karp et al.~also presented an extension of the {\sf Push-Pull} protocol together with a termination mechanism that spreads a rumor in $\Oh(\log n)$ rounds using only $\Oh(n \log \log n)$ messages. Doerr and Fouz~\cite{DF11} proposed a new protocol using only {\sf Push} calls that achieves a runtime of $(1+o(1)) \log_2 n$ using only $O(n \cdot f(n))$ calls (and messages), where $f(n)$ is an arbitrarily slowly growing function. Besides the complete graph, randomized rumor spreading protocols have been shown to be efficient also on other topologies. In particular, their runtime is at most logarithmic in $n$ for topologies ranging from basic networks, such as random graphs \cite{FPRU90,ES08,FHP10} and hypercubes \cite{FPRU90}, random regular graphs \cite{BEF08,FP10}, graphs with constant conductance \cite{MS08,CLP10,G11}, constant weak conductance \cite{HS10} or constant vertex expansion \cite{GS12,G13}, to more complex structures including preferential attachment graphs modeling social networks~\cite{CLP09}. In particular, recent studies establishing a sub-logarithmic runtime on certain social network models \cite{DFF11,DFF12,FPS12} raise the question whether it is possible to achieve a sub-logarithmic runtime also on the complete graph. In addition to analyses on static graphs, there are also studies on mobile geometric graphs, e.g.,~\cite{CPS13,PSSS11}. %, that deal with strong correlations as nodes are moving like random walks. Since all aforementioned protocols require $\Theta(\log n)$ rounds to spread the rumor on a complete graph, we equip nodes with the possibility of calling more than one node in each round. Specifically, we assume that the \emph{power} of a node $u$, denoted by $C_u$, is a random variable, which has the same distribution as a random variable $R$ with support on the positive integers and which is independent of $u$. In order to keep the overall communication cost small, we focus on distributions $R$ satisfying $\sum_{u \in V} C_u=\Oh(n)$ with high probability -- in particular, $R$ has bounded mean. Our aim is to understand the impact of the distribution of $R$ on the runtime of randomized rumor spreading. In particular, we seek for conditions on $R$ which are necessary (and/or sufficient) for a sublogarithmic runtime. Our first result concerns the {\sf Push} protocol for the case where $R$ has bounded mean and bounded variance, which is the most basic setting. Let $T_{total}$ be the first round in which all nodes are informed. \begin{thm}\label{thm:pushfinite} Consider the {\sf Push} protocol and assume that $R$ is a distribution with $\Ex{R}=\Oh(1)$ and $\Var{R}=\Oh(1)$. Then $|T_{total}-(\log_{1+\Ex{R}}n+\log_{\mathrm{e}^{\Ex{R}}}n)|=o(\ln n)$. \end{thm} Note that by putting $R \equiv 1$, we retain the classic result by Frieze and Grimmett. Our next result addresses the case where we drop the assumption on the variance, and it provides a lower bound of $\Omega(\log n)$ on the number of rounds. Although this result is less precise than \thmref{pushfinite}, it demonstrates that it is necessary to consider the {\sf Push-Pull} protocol in order to achieve a sub-logarithmic runtime. \begin{thm}\label{thm:push} Assume that $R$ is any distribution with $\Ex{R}=\Oh(1)$. Then with probability $1-o(1)$, the {\sf Push} protocol needs at least $\Omega(\log n)$ rounds to inform all nodes. \end{thm} We point out that the lower bound in \thmref{push} is tight up to constant factors, as the results in \cite{FG85,Pit87} for the standard {\sf Push} protocol imply an upper bound of $\Oh(\log n)$ rounds. We now consider the {\sf Push-Pull} protocol and extend the lower bound of $\Omega(\log n)$ from \thmref{pushfinite}. \begin{thm}\label{thm:pushpullfinite} Assume that $R$ is any distribution with $\Ex{R}=\Oh(1)$ and $\Var{R}=\Oh(1)$. Then for any constant $\epsilon > 0$, with probability $1-\epsilon$ the {\sf Push-Pull} protocol needs at least $\Omega(\log n)$ rounds to inform all nodes. \end{thm} \thmref{pushpullfinite} establishes that an unbounded variance is necessary to break the $\Omega(\log n)$ lower bound. An important distribution with bounded mean but unbounded variance is the {\em power law distribution} with exponent $\beta \leq3$, i.e., there are constants $0 < c_1 \leq c_2$ such that $c_1 z^{1-\beta} \leq \Pr{ R \geq z} \leq c_2 z^{1-\beta}$ for any $z \geq 1$, and $\Pr{ R \geq 1}=1$. We are especially interested in power law distributions, because they are scale invariant and have been observed in a variety of settings. Our main result below shows that this natural distribution achieves a sublogarithmic runtime. \begin{thm}\label{thm:pushpullpowerlaw} Assume that $R$ is a power law distribution with $2<\beta<3$. Then the {\sf Push-Pull} protocol informs all nodes in $\Theta(\ln\ln n)$ rounds with probability $1-o(1)$. \end{thm} Notice that if $R$ is a power law distribution with $\beta > 3$, then \thmref{pushpullfinite} applies because the variance of $R$ is bounded. Hence our results reveal a dichotomy in terms of the exponent $\beta$: if $2 < \beta < 3$, then the {\sf Push-Pull} protocol finishes in $\Oh(\log \log n)$ rounds, whereas for $\beta > 3$ the {\sf Push-Pull} protocol finishes in $\Theta(\log n)$ rounds \footnote{We do not consider the case $\beta \leq 2$, since then there exists at least one node with degree $\Omega(n)$ and the rumor is spread in constant time. Additionally, $\Ex{R}$ is no longer bounded.}. While a very similar dichotomy was shown in \cite{FPS12} for random graphs with a power law degree distribution, our result here concerns the spread of the rumor from one to {\em all} nodes. %In addition, the distribution of the edges used throughout the execution of the {\sf Push-Pull} protocol is different from the distribution of the edges in a power law random graph, as the latter is proportional to the product of the two nodes weights. Therefore it seems difficult to apply the previous techniques for power law random graphs used for the analysis of the average distance \cite{CL03} and rumor spreading \cite{FPS12}. %{\color{red} Besides the power law distribution, one may also consider a simple two-point distribution over sample space $\{1,x\}$, $x\in \mathbb{N}$, where $R=x$ with probability $\frac{1}{x}$ and $R=1$ otherwise. Then we show the following lemma: %\begin{thm}\label{thm:pushpulltwopoint} %Assume that $R_x$ be a two-point probability distribution with $x=n^{\delta}$, where $\delta=\Oh(1)$ and $16\leq x\leq \frac{n}{\log n}$. Then for any positive number $\epsilon$, with probability $1-\epsilon-o(1)$ the {\sf Push-Pull} protocol informs all nodes in at most $\frac{2}{\delta}+\Oh(\log \frac{1}{\epsilon})$ rounds. %%} %For any integer $x>1$, we define a two-point probability distribution $R_x$ over the sample space $\{1, x\}$ %, %where $x=n^{\Omega(1)}$,% for any $\delta=\Omega(1)$ %with probability density $\Pr{R_x=1}=1-\frac{1}{x}$ and $\Pr{R_x=x}=\frac{1}{x}$. %It is then straightforward to see that with constant probability, the {\sf Push-Pull} protocol informs all nodes in $\Oh(1)$ rounds. The same result also holds if $R=n^{\epsilon}$ with probability $n^{-\epsilon}$ and $R=1$ otherwise. In the case $\beta=3$ we show that the runtime is close to the one in the $\beta > 3$ case. \begin{thm}\label{thm:pushpullpowerlaw3} Assume that $R$ is a power law distribution with $\beta=3$. Then the {\sf Push-Pull} protocol informs all nodes in $\Theta\left(\frac{\ln n}{\ln\ln n}\right)$ rounds with probability $1-o(1)$. \end{thm} Finally, we also argue that it is necessary that the $C_u$'s are chosen once and for all at the beginning, and they are not updated in each round. Indeed, suppose we generate in the $t$th round a new variable $C_u^t$, which is the number of calls made by $u$ in that round. Then we prove the following lower bound. %lower bound of $\Omega(\log n)$ for the {\sf Push-Pull} protocol for any distribution $R$ with bounded mean (see \secref{newmodel} in the appendix for details). Based on this lower bound it seems crucial to have a {\em fixed} set of powerful nodes (i.e.~nodes $u$ with large $C_u$) in order to obtain a sublogarithmic rumor spreading time. \begin{thm}\label{thm:generator} Assume that $R$ is any distribution with $\Ex{R}=\Oh(1)$. Then with probability $1-o(1)$, the {\sf Push-Pull} protocol needs $\Omega(\ln n)$ rounds to inform all nodes. \end{thm} \section{Notations and Preliminaries} %We now provide additional definitions and notations (note that the classic {\sf Push}, {\sf Pull} and {\sf Push-Pull} protocols have been already defined in the introduction). Here we generalize the classic {\sf Push}, {\sf Pull} and {\sf Push-Pull} to the following statistical model on a complete graph with $n$ nodes. Before the protocol starts, every node $u$ generates a random integer $C_u\geq 1$ independent of each other according to a distribution $R$. Then, a piece of information (rumor, message, \ldots) is placed on an arbitrary node of the graph. We introduce some notation that will be used throughout the paper without further reference. In our setting, the {\sf Push}, {\sf Pull} and {\sf Push-Pull} protocols proceed like the classic ones except that in each round, every (un)informed node $u$ calls $C_u$ node(s) chosen independently and uniformly at random and sends (requests) the rumor. For any of these protocols, we let $\mathcal{I}_t$ be the set of informed nodes at the end of round $t$ and $\mathcal{U}_t$ the set of uninformed nodes. We write ${\cal V} = \mathcal{I}_t \cup \mathcal{U}_t$ for the vertex set of the graph, and we assume $|{\cal V}| = n$. The size of $\mathcal{I}_t$ and $\mathcal{U}_t$ is denoted by $I_t$ and $U_t$. We indicate the set of newly informed nodes in round $t+1$ by $\mathcal{N}_t$ and its size is $N_t$. Let $S_t$ be the number of {\sf Push} calls in round $t+1$, so $S_t=\sum_{u\in \mathcal{I}_t}C_u \geq I_t$. Let us define $\mathcal{N}_{t}^{{\sf Pull}}$ and $\mathcal{N}_{t}^{{\sf Push}}$ to be the set of newly informed nodes by {\sf Pull} and {\sf Push} calls in round $t+1$, respectively. The size of $\mathcal{N}_{t}^{{\sf Pull}}$ and $\mathcal{N}_{t}^{{\sf Push}}$ are denoted by $N_{t}^{{\sf Pull}}$ and $N_{t}^{{\sf Push}}$. The size of every set divided by $n$ will be denoted by the corresponding small letter, so $i_t$, $n_t$ and $s_t$ are used to denote $I_t/n$, $N_t/n$, and $S_t/n$, respectively. Further, let \[ \mathcal{L}(z):=\{u\in \mathcal{V}: C_u\geq z \} \quad \text{ and set } \quad L(z) =\mathcal{L}(z) . \] Moreover, let $\Delta = \max_{u\in \mathcal{V}} C_u$. We will use extensively the following two concentration inequalities. The first one is a Chernoff-type bound. \begin{thm}[\cite{DP09}]\label{DP09} Suppose that $X_1,X_2\ldots,X_n \in \{0,1\}$ are independent and identically distributed random variables and let $X:=\sum_{i=1}^{n}X_i$. Then for any $\lambda\geq0$ \[ \Pr{| X-\Ex{X} | \geq \lambda}\leq 2\cdot\mathrm{e}^{-\frac{\lambda^2}{2(\Ex{X}+\lambda/3)}}. \] In particular, \[ \Pr{ | X-\Ex{X} | \geq {\Ex{X}}/{2}}\leq 2\cdot\mathrm{e}^{-\frac{{\Ex{X}^2}}{8(\Ex{X}+\Ex{X}/6)}}< 2\cdot\mathrm{e}^{-\frac{\Ex{X}}{10}}. \] \end{thm} The next inequality is known as the Bounded Difference inequality. \begin{thm}[\cite{McD98}]\label{bounded} Suppose that $X_1,X_2\ldots,X_n$ are independent random variables and every $X_i$, $1\leq i\leq n$, takes a value from a finite set $A_i$. Let $f: \prod_{1\leq i\leq n}A_i \rightarrow \mathbb{R}$ be a real-valued function so that there exist $c_1,c_2,\ldots,c_n$ with \[ \sup_{x_1,x_2,\ldots,x_n,x_i'} |f(x_1,x_2,\ldots,x_i,\ldots,x_n)-f(x_1,x_2,\ldots,x_i',\ldots,x_n)| \leq c_i, \text{ for every $1\leq i\leq n$}. \] Then, for every $\lambda>0$, \[ \Pr{|f(X_1,X_2,\ldots,X_n)-\Ex{f(X_1,X_2,\ldots,X_n)}| \geq \lambda}\leq2\cdot \mathrm{e}^{-\frac{\lambda^2}{2\sum_{i=1}^nc^2_i}}. \] \end{thm} \section{Some Useful Facts for Power Law Distributions} Let $R$ be a power law probability distribution with exponent $\beta$, i.e., there are constants $0 < c_1< c_2$ so that for every integer $z \geq 1$, \[ c_1\cdot z^{1-\beta}\leq \Pr{C_u\geq z}\leq c_2\cdot z^{1-\beta}, \] and $\Pr{ C_u \geq 1} = 1$. In this section we collect some basic properties of $R$. \begin{fact}\label{factpowerlaw} If $R$ is a power law distribution with $\beta > 3$, then $\Var{R} = \Oh(1)$. \end{fact} \begin{proof} Since $\beta > 3$ \begin{align*} \Var{R} &\leq \Ex{ R^2} = \sum_{z\ge1} \Pro{R^2 \geq z} \leq 1 + \sum_{z\ge2} \sqrt{c_2\cdot z^{1-\beta}} < \infty. \end{align*} \end{proof} \begin{fact}\label{fact} Let $\beta > 2$. Let $C_u$, $u \in{\cal V}$ be independent, power-law distributed random variables with exponent $\beta$. Then, with probability $1-o(\frac{1}{\ln n})$, \[ \Delta :=\max_{u\in \mathcal{V} } C_u \leq n^{\frac{1}{\beta-1}}\cdot{\ln n}. \] \end{fact} \begin{proof} By definition, \[ \Pr{C_u\geq n^{\frac{1}{\beta-1}}\ln n}\leq {c_2\cdot n^{-1} \cdot \ln ^{1-\beta}(n)}. \] Applying the union bound yields the claim. %that with probability at least $1-\frac{c_2}{\ln^{\beta-1} n}=1-o(\frac{1}{\ln n})$ %\[ %\Delta\leq {n^{\frac{1}{\beta-1}}}{\ln n}. %\] \end{proof} Recall that $\mathcal{L}(z):=\{u\in \mathcal{V}, C_u\geq z\}$ and $L(z):=|\mathcal{L}(z)|$. \begin{pro}\label{bionom} Let $\beta > 2$. Let $C_u$, $u \in{\cal V}$ be independent, power-law distributed random variables with exponent $\beta$. Then, for every $z=\Oh( n^{\frac{1}{\beta-1}}/ \ln n)$, with probability $1-o({1}/{n})$ \begin{align*} \frac{n\cdot c_1\cdot z^{1-\beta}}{2} \leq {L}(z)\leq \frac{3\cdot n\cdot c_2\cdot z^{1-\beta}}{2}. \end{align*} \end{pro} \begin{proof} For $u\in \mathcal{V}$ let $I_u$ be the indicator random variable for the event $C_u \ge z$. Since the $C_u$'s are independent and identically distributed, so are the $I_u$'s. By linearity of expectation %\begin{align*} %c_1 \cdot Z^{1-\beta}\leq \Ex{{L}(Z)} n\cdot c_2 \cdot Z^{1-\beta}, %\end{align*} %and we have that \[ n\cdot c_1 \cdot z^{1-\beta}\leq \Ex{L(z)} \leq n\cdot c_2 \cdot z^{1-\beta}. \] Applying Theorem \ref{DP09} to the random variable $X:=\sum_{u\in \mathcal{V}}I_u$ yields that \begin{align*} \Pr{|{L}(z)-\Ex{L(z)}|>{\Ex{L(z)}}/{2}}< 2\cdot\mathrm{e}^{-\frac{\Ex{L(z)}}{10}}\leq 2\cdot\mathrm{e}^{-\frac{n\cdot c_1 \cdot z^{1-\beta}}{10}} \end{align*} Since $z=\Oh( n^{\frac{1}{\beta-1}}/\ln n) $, the claim follows. \end{proof} \section{Push Protocol} %\subsection{Preliminaries} In this section we will show two general lemmas for the {\sf Push} protocol that are valid for any $R$ with support on the positive integers. They will be used when analyzing the {\sf Push} and the {\sf Push-Pull} protocols. \begin{lem}\label{push0} Consider the {\sf Push} protocol and suppose that $S_t \leq\ln^c n$, where $c>0$ is an arbitrary constant. Then with probability at least $1-\Oh({n^{-1}\ln ^{2c}n})$ we have \begin{align*}\label{rec0} I_{t+1}=I_t+ S_t. \end{align*} \end{lem} \begin{proof} Recall that $S_t$ is the number of {\sf Push} calls in round $t+1$. By applying the union bound, the probability that an informed node receives a call in round $t+1$ is bounded by $\frac{S_t I_t}{n}$. So, with probability at least $1-\frac{S_t I_t}{n}$, none of the calls are sent to a node in $\mathcal{I}_t$. Conditioning on this event, consider all calls one by one in an arbitrary order; then the probability that the $i-$th call informs a different node from the previous $i-1$ calls is $1-\frac{i-1}{U_t}$. Therefore the conditional probability that $S_t$ calls inform $S_t$ different nodes is at least \[ \prod_{i=1}^{S_t-1} \left(1-\frac{i}{U_t}\right)>\left(1-\frac{S_t-1}{U_t}\right)^{S_t} \geq 1- \frac{S_t^2}{U_t} . \] So the probability that $S_t$ calls inform $S_t$ different uninformed nodes is at least \begin{align*} \left(1- \frac{S_tI_t}{n} \right)\cdot \left(1-\frac{S_t^2}{U_t} \right)=1-\Oh\left(\frac{S_t^2}{n}\right), \end{align*} where the above equality holds because $I_t\leq S_t \leq\ln^c n$ and $U_t=n(1-o(1))$. The claim follows. \end{proof} \begin{lem}\label{push3} Consider the {\sf Push} protocol. Then with probability at least $1-o(\frac{1}{\ln n})$ \begin{align*}\label{Nt} s_t-2s_t^2-2\sqrt{\frac{s_t\ln\ln n}{n}} \leq n_t\leq s_t. \end{align*} \end{lem} \begin{proof} Since $N_t$ is always bounded by $S_t$, $n_t\leq s_t$. To see the lower bound, let for $v\in \mathcal{U}_t$ $Z_v$ be the indicator random variable for the event $v\in \mathcal{I}_{t+1}$. Then $N_t=\sum_{v\in \mathcal{U}_t} Z_v.$ Since the $Z_v$'s are identically distributed random variables, \[ \Ex{N_t}=U_t\cdot\Pr{Z_v=1}. \] Let $X_i\in \mathcal{V}$, $1\leq i\leq N=S_t$, denote the target of the $i$-th call. Define \[ f(X_1,X_2,\ldots,X_N):=N_t\] to be the function counting the number of newly informed nodes in round $t+1$. Then $\Ex{f(X_1,X_2,\ldots,X_N)}=\Ex{N_t}$. For each change in just one coordinate of $f$, the following statement holds: \[ \sup_{x_1,x_2,\ldots,x_i,x_{i}' \in \mathcal{V}}|f(x_1,x_2,\ldots,x_i,\ldots,x_N)-f(x_1,x_2,\ldots,x_i',\ldots,x_N)|\leq 1. \] Therefore by applying Theorem \ref{bounded}, we obtain \[ \Pr{\big|N_t-\Ex{N_t}\big|\geq \sqrt{4\cdot S_t\cdot \ln\ln n}}\leq2\cdot\mathrm{e}^{{-4S_t\ln\ln n}/{2S_t}}=o\left({1}/{\ln n}\right). \] So with probability $1-o({1}/{\ln n})$ we have \begin{align}\label{concent} N_t>\Ex{N_t}-2\sqrt{S_t\ln\ln n}=U_t\cdot\Pr{Z_v=1}-2\sqrt{S_t\ln\ln n}. \end{align} Now we estimate $\Pr{Z_v=1}$. By the definition of {\sf Push} \[ \Pr{Z_v=1}=1-\prod_{u\in \mathcal{I}_t}\left(1-{{1}\over{n}}\right)^{C_u}. \] Using that $1-x \leq \mathrm{e}^{-x}\leq 1-x+x^2$ for any $x\geq0$ \begin{align*} \Pr{Z_v=1}&\geq 1-\mathrm{e}^{-\sum_{u\in \mathcal{I}_t} C_u/n}=1-\mathrm{e}^{-s_t} \geq s_t- s_t^2. \end{align*} We now plug the value obtained by the above formula into (\ref{concent}) and normalize it. So we obtain \begin{align*} n_t&\geq (1-i_t)\cdot\left(s_t- s_t^2\right)-2\sqrt{\frac{s_t\ln\ln n}{n}}\\ &= s_t-s_t^2-i_t\cdot\left(s_t-s_t^2\right) - 2\sqrt{ \frac{s_t\ln\ln n}{n} } \geq s_t-2s_t^2-2\sqrt{\frac{s_t\ln\ln n}{n}}, \end{align*} where the last inequality comes from the fact that $i_t\leq s_t$. \end{proof} \begin{cor}\label{pushnew} Consider the {\sf Push} protocol. %and suppose that $ S_t\geq \log n$. % and suppose that $s_t=\omega(\frac{\ln\ln n}{n})$. Then with probability at least $1-o({1}/{\ln n})$ for any round $t$ in which $S_t\leq {n}/{8}$ we have that $ I_{t+1}\geq I_{t}+{S_t}/{2}$. \end{cor} \begin{proof} If $1\leq S_t\leq \log n$, then Lemma \ref{push0} yields that with probability $1-o({1}/{\log n})$ we have $N_t=S_t$. If $\log n\leq S_t\leq {n}/{8}$, then $2s_t^2\leq {s_t}/{4}$ and $2\sqrt{{s_t n^{-1} \ln\ln n}}\leq {s_t}/{4}$. Thus, Lemma \ref{push3} guarantees that with probability at least $1-o({1}/{\ln n})$ %\[ %\frac{s_t}{2}\leq s_t-2s_t^2-2\sqrt{\frac{s_t\ln\ln n}{n}}. %\] %On the other hand,, \begin{align*} n_t \ge s_t-2s_t^2-2\sqrt{\frac{s_t\ln\ln n}{n}} \ge \frac{s_t}{2}. \end{align*} %Since $n_t$ is a non-decreasing function in terms of $s_t$, %the larger $S_t$ pushes the rumor to more uninformed nodes. I %in the case that $S_t\geq\frac{n}{8}$, using the above inequality results that with probability $1-o(\frac{1}{\log n})$ we have $N_t\geq \frac{n}{16}$. Therefore with probability $1-o(\frac{1}{\log n})$, for any round $t=\Oh(\log n)$ % the number of new informed nodes $n_t$ for any round $t$ in which $S_t\ge\frac{n}{8}$ we have that $n_t$ %is at least equal to $n_t$ for $S_t=\frac{n}{8}$. Therefore with probability $1-o(1)$, %\begin{align*} %I_{t+1}\geq I_{t}+\min\left\{\frac{S_t}{2}, \frac{n}{16}\right\}. %\end{align*} %$\geq n_{t'}$ for a round $t'$ (possibly does not exist ) in which $S_{t'}=\frac{n}{8}$. So $n_t\geq \frac{1}{16}$. %And the claim follows. \end{proof} \begin{cor}\label{exponential} Consider the {\sf Push} protocol. For any round $t$ and positive integer $k=\Oh(\log n)$ in which $S_{t+k}=o(n)$, with probability $1-o(\frac{k}{\log n})$ \[ I_{t+k}\geq I_t\cdot\left({3}/{2}\right)^k. \] \end{cor} \begin{proof} By assumption we have for every $1\leq i\leq k$ that $S_{t+i}=o(n)$. Applying Corollary \ref{pushnew} shows that with probability $1-o(\frac{1}{\log n})$ \[ I_{t+i}\geq I_{t+i-1}+\frac{S_{t+i-1}}{2}\geq I_{t+i-1}\cdot\frac{3}{2}. \] Using an inductive argument and the union bound for $k$ implies the statement. \end{proof} \section{Push Protocol with Bounded Mean and Bounded Variance}\label{sub:pushfinite} This section is devoted to the proof of Theorem \ref{thm:pushfinite}. Recall that $T_{total}:=\min\{ t ~|~ I_t = n\}$, i.e., the first round in which all nodes are informed. We claim that if $\Ex{R}=\Oh(1)$ and $\Var{R}=\Oh(1)$, then $|T_{total}-(\log_{1+\Ex{R}}n+\log_{\mathrm{e}^{\Ex{R}}}n)|=o(\ln n)$. To prove this result, we study the protocol in three consecutive phases. In the following we give a brief overview of the proof. \begin{itemize} \item{\bf The Preliminary Phase.} This phase starts with just one informed node and ends when $I_t\geq \ln ^5 n$. Similar to the proof of the birthday paradox we show that in each round every {\sf Push} call informs a different uninformed node and thus the number of informed nodes increases by $S_t\geq I_t$. Hence after $\Oh(\ln\ln n)$ rounds there are at least $\ln ^5 n$ informed nodes. Further, since $\Ex{R}=\Oh(1)$, after $\Oh(\ln\ln n)$ rounds we also have $S_t\leq \ln^{\Oh(1)}n$ for all these rounds. \item{\bf The Middle Phase.} This phase starts when $\ln ^5 n\leq I_t\leq S_t\leq \ln ^{\Oh(1)}n$ and ends when $I_t\geq {n}/{\ln\ln n}$. First we show that % that in round $t+1$ with probability $1-o(\frac{1}{\ln n})$, the number of {\sf Push} calls $S_t$ increases by a factor of approximately $1+\Ex{R}$ as long as the number of informed nodes is $o(n)$. Then we prove that the number of newly informed nodes in round $t+1$ is roughly the same as $S_t$. Therefore an inductive argument shows that it takes $\log_{1+\Ex{R}} n \pm o(\ln n)$ rounds to reach ${n}/{\ln\ln n}$ informed nodes. \item{\bf The Final Phase.} This phase starts when $I_t\geq \frac{n}{\ln\ln n}$ and ends when all nodes are informed with high probability. In this phase, we first prove that after $o(\ln n)$ rounds the number of uninformed nodes decreases to ${n}/{\ln^5 n}$. Then we show the probability that an arbitrary uninformed node remains uninformed is $e^{-\Ex{R}\pm o({1}/{\ln n})}$. Finally, an inductive argument establishes that it takes $\log_{\mathrm{e}^{\Ex{R}}} n\pm o(\ln n)$ rounds until every node is informed. \end{itemize} In the following we present the detailed proofs for these phases. Before that we show the following proposition. \begin{pro}\label{trick} Let $\epsilon > 0$ and let $R$ be a random variable with support on the positive integers such that $\Ex{R}=\Oh(1)$ and $\Var{R}=\Oh(1)$. Let $\delta \ge 0$ be such that $U_t=n^{1-\delta}$, for some round $t$. Then, with probability $1-o({1}/{\ln n})$, \[ \sum_{u\in \mathcal{U}_t}C_u=\Oh(n^{1-\delta/2} \cdot \ln^{1+\epsilon}n). \] \end{pro} \begin{proof} For $k \in \mathbb{N}$ let us define a random variable \[ W_k:=\sum_{u\in\mathcal{V}} C_u \cdot \mathbbm{1}(C_u\geq k). \] By linearity of expectation \begin{align*} \Ex{W_k}&=\sum_{u\in \mathcal{V}}\Ex{C_u \mathbbm{1}(C_u\geq k)}\\ &=n\cdot\Ex{C_u \mathbbm{1}(C_u\geq k)} =n\cdot\sum_{l\geq k}l\cdot\Pr{C_u=l}\leq\frac{n}{k}\cdot \sum_{l\geq k}l^2\cdot\Pr{C_u=l}. \end{align*} Since $C_u$ has bounded variance the last sum is in $\Oh(1)$. Thus, $\Ex{W_k}=\Oh({{n}/{k}})$. Markov's inequality implies that with probability $1-o({1}/{\ln n})$, $W_k=\Oh({{n\cdot \ln^{1+\epsilon} n \cdot k^{-1}}})$. If we set $k=n^{\delta/2}$, then \[ \sum_{u\in \mathcal{U}_t}C_u= \sum_{\{u\in\mathcal{U}_t \colon C_u\geq k\}}C_u ~~+\sum_{\{u\in\mathcal{U}_t \colon C_u< k\}}C_u~\leq W_k +\Oh(n^{1-\delta} \cdot k)= \Oh(n^{1-\delta/2}\cdot \ln ^{1+\epsilon}n). \] \end{proof} \subsection{The Preliminary Phase} This phase starts with one informed node and ends when $I_t\geq \ln^5 n$ and $S_t\leq \ln ^{\Oh(1)} n$. Let $T_0$ be the first round in which the number of informed nodes exceeds $\ln^5 n$. \begin{lem}\label{control} For any $t=\Oh(\ln\ln n)$, with probability at least $1-{\ln^{-3}n}$, we have $S_t=\ln ^{\Oh(1)}n$. \end{lem} \begin{proof} We will bound the expected number of calls in each round $t$ as follows: \[ \Ex{S_t \,| \, S_{t-1}}=S_{t-1}+\Ex{\sum_{u\in \mathcal{N}_{t-1}}C_u~\Big|~S_{t-1}}= S_{t-1}+N_{t-1}\cdot\Ex{R}\leq S_{t-1}\cdot(1+\Ex{R}), \] where the last inequality comes from the fact that $N_{t-1}\leq S_{t-1}$. Since the origin of the rumor is chosen before determining the $C_u$'s we have $\Ex{S_0}=\Ex{R}$. Applying the law of total expectation yields \[ \Ex{S_{t}}=\Ex{\ldots\Ex{\Ex{S_t \,|\, S_{t-1}} \,|\, S_{t-2}}\ldots \,|\, S_0}\leq (1+\Ex{R})^t\Ex{S_0}=(1+\Ex{R})^t\Ex{R}. \] By using Markov's inequality we have that \[ \Pr{S_t\geq (1+\Ex{R})^{t}\cdot \Ex{R}\cdot \ln^3n}\leq {\ln^{-3} n }. \] and the claim follows for any $t=\Oh(\ln\ln n)$. \end{proof} \begin{cor}\label{cor63} With probability $1-o(1)$ we have $T_0=\Oh(\ln\ln n)$. \end{cor} \begin{proof} Lemma \ref{control} asserts that with probability at least $1-\Oh({\ln^{-3} n})$, $S_t= \ln ^{\Oh(1)} n$ for any $t=\Oh(\ln\ln n)$. Conditioning on this event, Lemma \ref{push0} guarantees that with probability $1-(n^{-1} {\ln ^{\Oh(1)}n})$, for any $t=\Oh(\ln\ln n)$, \[ I_{t+1}=I_t+S_t\geq 2I_t, \] where the inequality comes from the fact that $S_t\geq I_t$. So, with probability at least \[ \left(1-\frac{1}{\ln ^3n}\right)\left(1-\Oh(\ln\ln n)\cdot \frac{\ln ^{\Oh(1)}n}{n} \right)=1-o(1), \] there exists a round $T_0=\Oh(\ln\ln n)$ such that $I_{T_0}\geq \ln^5 n$ and $S_{T_0}\leq \ln ^{\Oh(1)} n$. \end{proof} \subsection{ The Middle Phase } The phase starts when $ \ln ^5n\leq I_t\leq S_t\leq \ln^{\Oh(1)}n$ and ends when $I_t\geq {n}/{\ln\ln n}$. Let $T_1$ be the first round so that $I_{T_1} \geq {n}/{\ln\ln n}$. The main result of this subsection is that $|T_1-\log_{1+\Ex{R}}n|= o(\ln n)$ with high probability. \begin{lem}\label{message} %For push protocol with a distribution $R$ having finite mean and variance. Suppose for a round $t$ we have {$s_t=\Omega(n^{-1} \cdot {\ln^5 n})$ and $s_t=o(1)$}. Then for any $k=\Oh(\ln n)$ with $(1+\Ex{R})^ks_{t}=o(1)$, with probability $1-o({k}/{\ln n})$, \begin{align}\label{claim} \text{for all $1\leq i \leq k$, }~~(1+\Ex{R})^i\cdot s_t\cdot(1-o(1)) \leq s_{t+i}\leq(1+\Ex{R})^i\cdot s_t\cdot(1+o(1)). \end{align} \end{lem} \begin{proof} Consider the random variable $\sum_{u\in \mathcal{N}_t} C_u$. Since $\mathcal{N}_t$ is fixed and the random variables $C_u$, $u \in \mathcal{N}_t$ are independent we obtain that $\Ex{\sum_{u\in \mathcal{N}_t} C_u}=N_t\cdot\Ex{R}$. Moreover, \[ \Var{\sum_{u\in \mathcal{N}_t} C_u}=N_t\cdot\Var{R}. \] Chebychev's inequality implies that \[ \Pr{\Big|\sum_{u\in \mathcal{N}_t} C_u-N_t\Ex{R}\Big|\geq\sqrt{N_t\ln^{2} n }}\leq\frac{N_t\Var{R}}{N_t\ln ^2 n}=o\left(\frac{1}{\ln n}\right). \] Since $S_{t+1}=S_t+\sum_{u\in \mathcal{N}_t}C_u$, it follows that with probability $1-o({1}/{\ln n})$, \begin{align}\label{St0} S_t+N_t\cdot\Ex{R}-\sqrt{N_t\ln^{2}n}\leq S_{t+1}\leq S_t+N_t\cdot\Ex{R}+\sqrt{N_t\ln^{2}n}. \end{align} Using the above formula and the fact that $N_t\leq S_t$ we have \begin{align*} S_{t+1}&\leq S_t+S_t\cdot\Ex{R}+\sqrt{S_t\ln^{2}n} \leq S_t\cdot\left(1+\Ex{R}+\sqrt{\frac{\ln^{2}n}{S_t}}\right). \end{align*} Since $S_t$ is a non-decreasing function in $t$ and $\ln^5 n\leq I_t\leq S_t$, with probability $1-o({1}/{\ln n})$ \begin{align*} s_{t+1}&\leq s_t\cdot(1+\Ex{R})\left(1+\sqrt{\frac{\ln^{2} n}{(1+\Ex{R})^2\ln ^5n}}\right) < s_t\cdot(1+\Ex{R})\left(1+\frac{1}{\ln ^{\frac{3}{2}}n}\right). \end{align*} An inductive argument and the union bound for all $ k$ events that violate the above inequality shows that for any $k=\Oh({\ln n})$ with probability $1-o({k}/{\ln n})$, \begin{align}\label{St} \text{for all $1\leq i\leq k$,}~~s_{t+i}\leq s_t\cdot(1+\Ex{R})^i\left(1+o(1)\right). \end{align} In order to prove the left hand side of (\ref{claim}), we use Lemma \ref{push3} which states with probability $1-o({1}/{\ln n})$, \[ n_t\geq s_t-2s^2_t-2\sqrt{\frac{s_t\ln\ln n}{n}}. \] Using the lower bound in (\ref{St0}) and the above formula implies that with probability $1-o({1}/{\ln n})$, \begin{align*} s_{t+1}&\geq s_t +n_t\cdot\Ex{R}-\sqrt{\frac{n_t\ln^2 n}{n}}\\ &\geq s_t+s_t\cdot\Ex{R}-2s_t^2\cdot\Ex{R}-2\sqrt{\frac{s_t\ln\ln n}{n}}\cdot\Ex{R}-\sqrt{\frac{s_t\cdot\ln^2 n}{n}}\\ &\geq (1+\Ex{R})s_t- 2\Ex{R}s_t^2-2\sqrt{\frac{s_t\ln^{2} n}{n}}\\ &\geq (1+\Ex{R})s_t-F(s_t), \end{align*} where $F(s_t)=2\Ex{R}s^2_t+2\sqrt{{n^{-1} \cdot s_t \cdot \ln^{2}n}}$. An inductive argument and the union bound for all $ k$ events that violate the above inequality show that for any integer $k$ for which $(1+\Ex{R})^k\cdot s_t=o(1)$ with probability $1-o({k}/{\ln n})$, \begin{align}\label{induc} \text{for all $1\leq i\leq k$},~~s_{t+i}\geq (1+\Ex{R})^i s_t-\sum_{j=0}^{i-1}(1+\Ex{R})^j F(s_{t+i-j}). \end{align} Inequality (\ref{St}) yields that with probability $1-o({k}/{\ln n})$, \[ \text{for all $1\leq i\leq k=\Oh(\ln n)$,}\quad s_{t+i}\leq a\cdot s_t\cdot(1+\Ex{R})^i, \] where $a:=1+o(1)$. $F(s_t)$ is a non-decreasing function in $s_t$ and hence for any $k=\Oh(\ln n)$ and $1 \leq j\leq k$, \begin{align*} F(s_{t+i-j})&\leq F( a\cdot(1+\Ex{R})^{i-j}s_t)\\ &\leq 2\Ex{R}(1+\Ex{R})^{2(i-j)}(a\cdot s_t)^2+2(1+\Ex{R})^{\frac{i-j}{2}}\sqrt{\frac{a\cdot s_t\ln^{2}n}{n}}. %&\leq\left\{\left(1+\Ex{R}\right)^{2(k-i)}+\left(1+\Ex{R}\right)^{\frac{k-i}{2}}\right\} F(c\cdot s_t). \end{align*} Hence by combining the above inequality and (\ref{induc}), we conclude that for any integer $k$, where $(1+\Ex{R})^ks_t=o(1)$ and $k=\Oh(\ln n)$ with probability $1-o({k}/{\ln n})$, for all $1\leq i\leq k$ \begin{align*} & s_{t+i}\\ &\geq (1+\Ex{R})^is_t-2\Ex{R}\sum_{j=0}^{i-1}(1+\Ex{R})^{2i-j}(c\cdot s_t)^2-2\sum_{j=0}^{i-1}(1+\Ex{R})^{\frac{i+j}{2}}\sqrt{\frac{c\cdot s_t\ln^{2} n}{n}}\\ &\geq (1+\Ex{R})^is_t - d_1\cdot (1+\Ex{R})^{2i}s_t^2 -d_2 \cdot (1+\Ex{R})^{i} \cdot \sqrt{\frac{s_t\ln^{2} n}{n}}\\ &= (1+\Ex{R})^is_t\cdot\left(1-d_1\cdot (1+\Ex{R})^{i}s_t -d_2 \cdot \sqrt{\frac{\ln^{2} n}{s_tn}}\right), \end{align*} where $d_1$ and $d_2$ are constants which do not depend on $i$. Since $(1+\Ex{R})^{k}s_t=o(1)$ and $s_t=\Omega(\frac{\ln^5 n}{n})$, for any $1\leq i\leq k$, \[ s_{t+i}\geq (1+\Ex{R})^i\cdot s_t\cdot (1-o(1)). \] \end{proof} \begin{lem}\label{pushm} Suppose that $\frac{\ln^5n }{n}\leq i_t\leq s_t\leq \frac{\ln^{\Oh(1)} n}{n}$. Then for any $k=\Oh(\ln n)$ with $(1+\Ex{R})^ks_{t}=o(1)$, with probability $1-o(1)$, \[ i_t+ f_2\cdot(1+\Ex{R})^{k}\cdot s_t\cdot(1-o(1)) \leq i_{t+k}\leq i_t+ f_1\cdot(1+\Ex{R})^{k}\cdot s_t\cdot(1+o(1)), \] where $f_1>0$ and $f_2>0$ are constants. \end{lem} \begin{proof} It is easy to see that \[ i_{t+k}=i_t+\sum_{i=0}^{k-1}n_{t+i} \leq i_t+\sum_{i=0}^{k-1}s_{t+i}. \] Applying Lemma \ref{message} implies that for any integer $k$ for which $(1+\Ex{R})^k\cdot s_t=o(1)$, with probability $1-o(\frac{k}{\ln n})$ the following upper bound holds: \begin{align*}%\label{upperXX} % CSG: label not used, and was multiply defined i_{t+k}\leq i_t +\sum_{i=0}^{k-1}s_{t+i} &\leq i_t+ s_t\cdot (1+o(1))\cdot\sum_{i=0}^{k-1}(1+\Ex{R})^i\notag\\ &=i_{t}+f_1\cdot(1+\Ex{R})^k\cdot s_t\cdot (1+o(1)), \end{align*} where $f_1>0$ is a constant. On the other hand, Lemma \ref{push3} yields that with probability $1-o(\frac{1}{\ln n})$, \[ n_t\geq s_t-2s^2_t-2\sqrt{\frac{s_t\ln\ln n}{n}}. \] Another application of Lemma \ref{message} shows that with probability $1-o(\frac{k}{\ln n})$, for all integers $1\leq i\leq k$ in which $(1+\Ex{R})^ks_t=o(1)$ and $s_t\geq \frac{\ln ^5 n}{n}$, \[ (1+\Ex{R})^i \cdot s_t\cdot(1-o(1))\leq s_{t+i}\leq (1+\Ex{R})^i\cdot s_t\cdot (1+o(1)). \] Using these two inequalities, as long as $(1+\Ex{R})^ks_t=o(1)$, we have with probability $1-o(\frac{k}{\ln n})$, \begin{align} &i_{t+k}=i_t+\sum_{i=0}^{k-1}n_{t+i} \nonumber\\ &\geq i_t+\sum_{i=0}^{k-1} s_{t+i}-\sum_{i=0}^{k-1}\left\{2 s^2_{t+i}+2\sqrt{\frac{s_{t+i}\ln\ln n}{n}}\right\}\nonumber\\ &\geq i_t+(1-o(1))\sum_{i=0}^{k-1}(1+\Ex{R})^is_t\nonumber\\ &~~~~~~-(2+o(1))\sum_{i=0}^{k-1}\left\{(1+\Ex{R})^{2i}s^2_t+(1+\Ex{R})^{i/2}\sqrt{\frac{s_{t}\ln\ln n}{n}}\right\}\nonumber\\ &\geq i_t+ f_2\cdot(1+\Ex{R})^{k}\cdot s_t -d\cdot \left( (1+\Ex{R})^{2k}s^2_t+(1+\Ex{R})^{k/2} \sqrt{\frac{s_{t}\ln\ln n}{n}} \right)\nonumber\\ &\geq i_t+ f_2\cdot(1+\Ex{R})^{k}\cdot s_t\cdot \left(1-f\cdot (1+\Ex{R})^{k}\cdot s_t-d\cdot (1+\Ex{R})^{-k/2}\sqrt{\frac{\ln\ln n}{s_t n}} \right), \label{lower} \end{align} where $f_2>0$ and $d>0$ are constants. Since $\frac{\ln^5 n}{n}\leq i_t\leq s_t$, we obtain that \begin{align} i_{t+k} &\geq i_t+ f_2\cdot(1+\Ex{R})^{k}\cdot s_t\cdot (1-o(1)). \label{upper} \end{align} By combining equations (\ref{upper}) and (\ref{lower}) we infer that with probability $1-o(\frac{k}{\ln n}),$ \[ i_t+ f_2\cdot(1+\Ex{R})^{k}\cdot s_t\cdot(1-o(1)) \leq i_{t+k}\leq i_t+ f_1\cdot(1+\Ex{R})^{k}\cdot s_t\cdot(1+o(1)). \] \end{proof} \begin{cor}\label{cor6} With probability $1-o(1)$ we have $|T_1-\log_{1+\Ex{R}}n|=o(\ln n)$. \end{cor} \begin{proof} Applying Corollary \ref{cor63} shows that with probability $1-o(1)$, $T_0=\Oh(\ln\ln n)$, where $T_0$ is the first round in which $\frac{\ln^5n}{n}\leq i_{T_0}\leq s_{T_0}\leq \frac{\ln^{\Oh(1)} n }{n}$. Now we can apply Lemma \ref{pushm} and set $k=\log_{1+\Ex{R}}n-o(\ln n)$ such that with probability at least $1-o(1)$ we have $\frac{1}{\ln \ln n}\leq i_{T_0+k}\leq \frac{A}{\ln \ln n}$, where $A>1$ is a constant. Then we conclude that with probability $1-o(1)$, $|T_1-\log_{1+\Ex{R}}n|=o(\ln n)$. \end{proof} \subsection{The Final Phase} This phase starts with at least $\frac{n}{\ln\ln n}$ informed nodes and ends when all nodes get informed. Let $T_1$ be the first round in which $I_{T_1}\geq \frac{n}{\ln\ln n}$ and let $T_2$ be the first round in which all nodes are informed with probability $1-o(1)$. We will show that with probability $1-o(1)$, $|(T_2-T_1)-\log_{e^{\Ex{R}}}n|= o(\ln n)$. %Before we prove the main result we show the following Proposition. \begin{lem} With probability $1-o(1)$, \[ |(T_2-T_1)-\log_{e^{\Ex{R}}}n|=o(\ln n). \] \end{lem} \begin{proof} We define the indicator random variable $Z_v$ for every $v\in \mathcal{U}_t$ and any round $t\geq T_1$: \[ Z_v= \left\{ \begin{array}{l l} 1 & \quad \text{if $v$ does not get informed in round t+1, }\\ 0 & \quad \text{otherwise.}\\ \end{array} \right. \] Thus, \begin{align*} \Ex{U_{t+1} \,|\, U_{t}}=\Ex{\sum_{v\in \mathcal{U}_t}Z_v}=U_t\cdot\Pr{Z_v=1}, \end{align*} where for simplicity we omit the conditioning of $U_{t+1}$ on $U_t$ when dealing with the $Z_v$'s. Using the fact that $1-\frac{1}{n}=e^{-\frac{1}{n}-\Oh(\frac{1}{n^2})}$, we can approximate the value $\Pr{Z_v=1}$ as follows, \begin{align*} \Pr{Z_v=1}&=\prod_{u\in \mathcal{I}_t}\left(1-\frac{1}{n}\right)^{C_u}=\prod_{u\in \mathcal{I}_t}e^{-\frac{C_u}{n}-\Oh(\frac{C_u}{n^2})}\\ &=e^{-\sum_{u\in \mathcal{I}_t}(\frac{C_u}{n}+\Oh(\frac{C_u}{n^2})) }=e^{-s_t-\Oh(\frac{s_t}{n})}. \end{align*} Since $\frac{s_t}{n}=\Oh(\frac{1}{n})$ for any round and $\mathrm{e}^{-\Oh(\frac{1}{n})}=1-\Oh(\frac{1}{n})$, \begin{align}\label{exp} \Ex{U_{t+1} \,|\, U_t}=U_te^{-s_t}\cdot e^{-\Oh({\frac{1}{n}})}=U_te^{-s_t}-\Oh\left(\frac{U_t}{n}\right). \end{align} Since for every $u, v\in \mathcal{U}_t$, \[ \Pr{Z_u=1\cap Z_v=1}=\Pr{Z_u=1~|~Z_v=1}\cdot\Pr{Z_v=1}\leq\Pr{Z_v=1}\cdot\Pr{Z_u=1}, \] we have that \[ \Ex{Z_u\cdot Z_v}\leq\Ex{Z_u}\cdot\Ex{Z_v}. \] Therefore, \begin{align*} \Var{\sum_{v\in \mathcal{U}_t}Z_v}&=\sum_{v\in \mathcal{U}_t} \Ex{Z^2_v}+\sum_{u\neq v}(\Ex{Z_u\cdot Z_v}- \Ex{Z_u}\cdot\Ex{ Z_v})\\ &\leq \sum_{v\in \mathcal{U}_t} \Ex{Z^2_v} = U_t\cdot\Pr{Z_v=1}=\Ex{U_{t+1}~|~U_t}\leq U_t. \end{align*} Applying Chebychev's inequality implies that with probability $1-o(\frac{1}{\ln n})$, \begin{align}\label{rec1} \Big|U_{t+1}-\Ex{U_{t+1}\,|\,U_t}\Big|\leq\sqrt{U_t\ln^{2}n }. \end{align} Combining inequalities (\ref{exp}) and (\ref{rec1}) yields that with probability $1-o(\frac{1}{\ln n})$, \begin{align}\label{rec2} \left|U_{t+1}-U_{t}e^{-s_t}\right|\leq\sqrt{U_t\ln^{2}n}+\Oh\left(\frac{U_t}{n}\right)\leq 2\sqrt{U_t\ln^{2}n}. \end{align} According to the value of $U_t$, we consider two cases. \begin{itemize} \item Suppose that $U_t\geq \frac{n}{\ln^5n}$. Note that $s_t\geq i_t\geq \frac{1}{\ln\ln n}$ by the assumption of the lemma. Since $s_t$ is a non-decreasing value in $t$ and $U_t0$ is a constant. \item Suppose that $U_t\leq \frac{n}{\ln^5 n}$. If we set $n^\delta=\ln^5n$, then applying Proposition \ref{trick} implies that for any $t$ for which $U_t=\Oh(\frac{n}{\ln^5 n})$ with probability $1-o(\frac{1}{\ln n})$, \begin{align}\label{Utrick} \sum_{u\in \mathcal{U}_t}C_u=o\left(\frac{n}{\ln n}\right). \end{align} On the other hand, using Chebychev's inequality yields that with probability $1-o(\frac{1}{\ln n})$, \[ \left|\sum_{u\in \mathcal{V}}C_u- n\cdot\Ex{R}\right|\leq\sqrt{n\cdot \ln ^{2}n}. \] Combining the above equality and equality (\ref{Utrick}) results into an approximation for $s_t$ which is not best possible but it suffices for our purpose. We know that \begin{align*} s_t&=\sum_{u\in \mathcal{V}}C_u-\sum_{u\in \mathcal{U}_t}C_u. \end{align*} So, \begin{align*} \Ex{R}- \sqrt{\frac{\ln^{2}n}{n}}-o\left(\frac{1}{\ln n}\right)\leq s_t \leq \Ex{R}+\sqrt{\frac{\ln^{2}n}{n}}. \end{align*} Therefore, $s_t$ can be replaced by $\Ex{R}\pm o(\frac{1}{\ln n})$ with probability $1-o(\frac{1}{\ln n})$. Inequality (\ref{rec2}) implies that \begin{align}\label{Ut} \alpha\cdot U_t-2\sqrt{U_t\ln^{2}n } \leq U_{t+1}\leq \alpha\cdot U_t+2\sqrt{U_t\ln^{2}n }, \end{align} where $\alpha=e^{{-\Ex{R}\pm o(1/\ln n)}}$. So as long as $U_t\geq \ln^5 n$ with probability $1-o(\frac{1}{\ln n})$, \begin{align*} U_{t+1} \leq \alpha \cdot U_t+2\sqrt{U_t\ln^{2} n} &= \alpha\cdot U_t \left(1+2\sqrt{\frac{\ln^{2}n}{\alpha^2 U_t}}\right) \\ &\leq \alpha\cdot U_t\left(1+2\sqrt{\frac{\ln^{2}n}{\alpha^2 \ln ^5 n}}\right) \leq \alpha\cdot U_t \left(1+\frac{2}{\alpha \ln ^{\frac{3}{2}}n}\right). \end{align*} Now for any $k$ for which $U_{t}e^{-k\Ex{R}}\geq \ln^{5} n$, with probability $1-o(\frac{k}{\ln n})$, \begin{align}\label{upperU} U_{t+k}\leq \alpha^k\cdot U_t \cdot \left(1+\frac{2}{\alpha \ln ^{\frac{3}{2}}n}\right)^k= \alpha^k\cdot U_t \cdot(1+o(1)). \end{align} In order to lower bound $U_{t+k}$ we apply the lower bound (\ref{Ut}) inductively. So we have that with probability $1-o(\frac{k}{\ln n})$, \begin{align*} U_{t+k}\geq \alpha^k\cdot U_t-\sum_{i=0}^{k-1}2\cdot\alpha^i\cdot\sqrt{U_{t+k-i-1}\ln ^{2}n}. \end{align*} Applying inequality (\ref{upperU}) yields that with probability $1-o(\frac{k}{\ln n})$, \[ \sqrt{U_{t+k-i}\ln ^{2}n}\leq \alpha^{\frac{k-i}{2}}\cdot\sqrt{U_{t}(1+o(1))\ln ^{2}n}. \] Thus, \begin{align}\label{lowerU} U_{t+k}&\geq \alpha^k\cdot U_t-(1+o(1))\sum_{i=0}^{k-1}\alpha^{\frac{k-i-1}{2}}\cdot\sqrt{U_{t}\ln ^{2}n}\nonumber\\ &\geq \alpha^k \cdot U_t-c\cdot\alpha^{\frac{k}{2}}\cdot\sqrt{U_{t}\ln ^{2}n} , \end{align} where $c>0$ is a constant and the last inequality holds because $\sum_{i=0}^{k-1}\alpha^{\frac{k-i-1}{2}}=\Oh(\alpha^{\frac{k}{2}})$. Combining the inequalities (\ref{upperU}) and (\ref{lowerU}) yields for any $k$ satisfying \[ U_{t}e^{-k\Ex{R}}\geq \ln^{5} n\] with probability $1-o(\frac{k}{\ln n})$, \[ \alpha^k\cdot U_t(1-o(1)) \leq U_{t+k}\leq \alpha^k \cdot U_t(1+o(1)). \] Hence by taking $k=\log_{e^{\Ex{R}}}n-o(\ln n)$, with probability $1-o(1)$, the number of uninformed nodes after $T_1+k_0+k$ rounds decreases to $\ln ^5 n$, so we have at most $\ln^5n$ uninformed nodes. Using the fact that for every $x\geq 0$, $1-x \leq e^{-x}$, the probability that a node does not get informed after $k_1$ additional rounds is bounded from above by \[ \prod_{u\in \mathcal{I}_t}\left(1-\frac{1}{n}\right)^{C_u\cdot k_1}\leq e^{-k_1\sum_{u\in \mathcal{I}_t}C_u}. \] We already know that $s_t=\Ex{R} \pm o(\frac{1}{\ln n})$ and $s_t$ is an non-decreasing value in $t$ so \[ \sum_{u\in \mathcal{I}_t}C_u= s_t>\frac{\Ex{R}}{2}. \] Thus the union bound implies that the probability that every node in $\mathcal{U}_t$ does not get informed is bounded by $\ln^5 n\cdot e^{\frac{-k_1\cdot \Ex{R}}{2}}$. By choosing $k_1=\Theta(\ln\ln n)$ we conclude that with probability $1-o(1)$ all nodes get informed. So we have with probability at least $1-o(1)$ that $T_2 \leq T_1+k_0+k+k_1$, and $k_0+k+k_1 = \log_{e^{\Ex{R}}}n + o(\ln n)$. %\NOTE{Thomas}{Shouldn't this part be outside the proof of this Lemma??} % \NOTE{ali}{why? we already stated this in the statement of lemma } Applying the concentration result to $T_1$ (Corollary \ref{cor6}) implies that %\[ %|T_{total}-T_1-\log_{e^{\Ex{R}}}n|=|T_{total}-(\log_{1+\Ex{R}}n+\log_{e^{\Ex{R}}}n)|=o(\ln n). %\] \end{itemize} \end{proof} \section{Push Protocol with Bounded Mean }\label{sub:pushmean} This section is devoted to the proof of \thmref{push}. \begin{proof} In the {\sf Push} protocol, in round $t+1$, at most $S_t$ randomly chosen uninformed nodes are informed. This implies that $\Ex{S_{t+1} \,|\, S_t}$ increases by at most $\Ex{R} \cdot S_t$. Since the origin of the rumor is chosen without knowing $C_u$ , $\Ex{S_0}=\Ex{R}$. Using the law of total expectation yields that \[ \Ex{S_{t}}=\Ex{\ldots\Ex{\Ex{S_t|S_{t-1}}|S_{t-2}}\ldots |S_0}\leq \left(1+\Ex{R}\right)^t\cdot\Ex{R}. \] By applying Markov's inequality, we conclude that \[ \Pr{I_t\geq n}\leq \Pr{S_t\geq n}\leq \frac{(1+\Ex{R})^t\cdot\Ex{R}}{n}. \] Hence $\Omega(\ln n)$ rounds are necessary to inform all nodes with probability $1-o(1)$. \end{proof} \section{Lower Bound for Push-Pull} Before we present our results about the {\sf Push-Pull} protocol we show the following general lemma. Recall that $S_0=C_u$, where $u$ is the single node that is aware of the rumor at the beginning of the protocol. \begin{lem}\label{pushpull0} Consider the {\sf Push-Pull} protocol and $\{C_u : u\in \mathcal{V}\}$ be a sequence of positive integers. Then with probability $1-o(1)$, the {\sf Push-Pull} protocol needs at least $$\Omega\left(\frac{\log n-\log S_0}{\log \sum_{u \in \mathcal{V}}{C_u^2}/{n}}\right)$$ rounds to inform all nodes. \end{lem} \begin{proof} We know the probability that an uninformed node $u$ gets informed by {\sf Pull} in round $t+1$ is bounded by ${I_t\cdot C_u}/{n}$. Therefore using this bound we have \begin{align*} &\sum_{u\in \mathcal{U}_t}\Ex{C_u \mathbbm{1}(\text{$u$ gets informed by {\sf Pull}})~|~S_t}\\ &=\sum_{u\in \mathcal{U}_t}C_u\cdot\Pr{\text{$u$ gets informed by {\sf Pull} in round $t+1$}}\\ &\leq \sum_{u\in \mathcal{U}_t} C_u \cdot \frac{I_t\cdot C_u}{n} \leq I_t\cdot\sum_{u\in \mathcal{V}} \frac{C_u^2}{n}%=\Oh\left(I_t\cdot \frac{\Ex{R^2}}{\epsilon}\right). \label{bound1} \end{align*} On the other hand the probability that a node $u\in \mathcal{U}_t$ gets informed by {\sf Push} in round $t+1$ is at most ${S_t}/{n}$. So we get that \begin{align*} &\sum_{u\in \mathcal{U}_t}\Ex{C_u \mathbbm{1}(\text{$u$ gets informed by {\sf Push}})~|~S_t} \\&=\sum_{u\in \mathcal{U}_t}C_u\cdot\Pr{\text{$u$ gets informed by {\sf Push} in round $t+1$}}\\ &\leq \sum_{u\in \mathcal{U}_t} C_u \cdot \frac{S_t}{n} \leq S_t\cdot\sum_{u\in \mathcal{V}} \frac{C_u^2}{n}, \end{align*} where the last inequality follows by $C_u\leq C_u^2$. Combining the above inequalities implies that \begin{align*} \Ex{S_{t+1} \,|\, S_t}\leq S_t + (S_t + I_t)\cdot\left(\sum_{u\in \mathcal{V}} {C_u^2}/{n}\right)\cdot \leq \left(1+2\cdot\sum_{u\in \mathcal{V}} {C_u^2}/{n}\right)\cdot S_t, \end{align*} %where $C>0$ is a constant. Since we are assuming that the sequence $\{ C_u \colon u \in {\cal V}\}$ is good, $S_0 = \Oh(1)$. Applying the law of total expectation yields that \[ \Ex{S_{t}}=\Ex{\ldots\Ex{\Ex{S_t|S_{t-1}}|S_{t-2}}\ldots |S_0}\leq \left(1+2\cdot\sum_{u\in \mathcal{V}} {C_u^2}/{n}\right)^t\cdot S_0. \] Using Markov's inequality implies that \[ \Pr{I_t=n}\leq \Pr{S_t>{n/2}}\leq \frac{\Ex{S_t}}{{n/2}}\leq \frac{\left(1+2\cdot\sum_{u\in \mathcal{V}} {C_u^2}/{n}\right)^t\cdot S_0}{{n/2}}, \] and the claim follows. \end{proof} \section{Push-Pull Protocol with Bounded Mean and Bounded Variance } This section is devoted to the proof of \thmref{pushpullfinite}. \begin{proof} $\{ C_u \colon u\in\mathcal{V}\}$ be a sequence of positive integers each of which is generated independently according to some distribution $R$ with $\Ex{R}=\Oh(1)$ and $\Var{R}=\Oh(1)$. We call $\{ C_u \colon u\in\mathcal{V} \}$ a {\it good} sequence if $\sum_{u\in \mathcal{V}}C^2_u=\Oh(n)$ and $S_0=\Oh(1)$. Since the origin of the rumor is chosen without knowing $C_u$, $\Ex{S_0}=\Ex{R}$. Applying Markov's inequality implies that for any constant $\epsilon > 0$ with probability at least $1-\epsilon/2$, $S_0=\Oh(1)$. Since $R$ is a probability distribution with bounded variance, $\sum_{u\in \mathcal{V}}\Ex{C_u^2}=\Oh(n)$. Another application of Markov's inequality implies that with probability $1-\epsilon/2$, $\sum_{u\in \mathcal{V}}{C_u^2}=\Oh(n)$. %$\sum_{u\in \mathcal{V}}C_u=\Oh(n)$. Therefore using a union bound for failure probability of two mentioned events implies that for fixed $\epsilon>0$ with probability at least $1-{\epsilon}$, $\{ C_u \colon u\in\mathcal{V} \}$ is a good sequence. %Then we conclude that with probability $1-\epsilon$, $\sum_{u\mathcal{V}}\frac{C_u^2}{n}=\Oh(1)$. Conditioning on the event that $\{ C_u \colon u\in\mathcal{V}\}$ is a good sequence, using Lemma \ref{pushpull0} implies that with probability at least $1-o(1)$ the {\sf Push-Pull} protocol needs $\Omega(\ln n)$ rounds to inform $n$ nodes and the result follows. \end{proof} \section{Push-Pull Protocol with Power Law Distribution $2<\beta<3$ }\label{sub:pushpullpowerlaw} In this section we analyze the {\sf Push-Pull} protocol where $R$ is a power law distribution with $2<\beta<3$ and show that it only takes $\Theta(\log \log n)$ rounds to inform all with probability $1 - o(1)$. To prove the upper bound of $\Oh(\log\log n)$, we study the protocol in three consecutive phases and show that each phase takes only $\Oh(\log\log n)$ rounds. After that we show the lower bound $\Omega(\log\log n)$. \subsection{Proof of the Upper Bound} %\red{ In the following %we give a brief overview of the proof. A complete proof for the lower and upper bound is given in Section \ref{B} in appendix. To prove a $\Omega(\log\log n)$ lower bound, %we start with a sequence $C_u$, $u\in \mathcal{V}$, where every $C_u$ is generated according to a power law distribution with $2<\beta<3$. Then we partition the set $\mathcal{V} $ to sets %$\mathcal{M}_i:=\{u\in\mathcal{V} : 2^{i-1}\leq C_u\leq 2^{i}\}$ for $i=1\ldots i^*$, where $i^*=\Oh(\log n)$. In the following we claim that in each round $t+1$ with probability %$1-o(\frac{1}{\log n})$ there exists $1\leq i_t\leq i^*$ so that no uninformed node in $\cup_{i=i_t}^{i^*}\mathcal{M}_i$ gets informed by {\sf Pull} call. Conditioning on this event, we can fairly bound the total %contribution of newly informed nodes to $\Ex{S_{t+1} | S_t}$. Hence we have $\Ex{S_{t+1} ~|~ S_t}\leq S_t^{(2+b)}$, where $b>0$ is a constant. So applying law of total expectation implies that $\Ex{S_{t+1}}\leq %S_t^{(2+b)^t}$. Therefore Markov's inequality results into a $\Omega(\log\log n)$ lower bound with high probability. % } %\paragraph{The Preliminary Phase.} \subsubsection*{The Preliminary Phase.} This phase starts with just one informed node and ends when $I_t\geq{n^{\frac{1}{\beta-1}}}/(2\cdot\ln n)$. Let $T_1$ be the first round where $I_{T_1}\geq n^{\frac{1}{\beta-1}}/(2\ln n)$. We will show that $T_1=\Oh(\log\log n)$. First we claim that $\Oh(\ln\ln n)$ rounds are sufficient to have $\ln ^{\Oh(1)} n$ informed nodes. Then we will show that in round $t+1$ with probability $1-e^{-\Omega(\ln n)}$ there exists a node $u$ with $ C_u \geq I_t^{ 1+\gamma}$, $\gamma:=\frac{3-\beta}{2(\beta-2)}>0$, which pulls the rumor and consequently $S_{t+1} \geq I_t^{1+\gamma}$. Then considering only {\sf Push} calls it follows that with probability $1-o(\frac{1}{\ln n})$, \[ I_{t+2}= I_{t+1}+N_{t+1}\geq I_{t+1}+S_{t+1}(1-o(1))>\frac{1}{2} I_t^{1+\gamma}. \] So in every two rounds, $I_t$ is increased by a factor of $\frac{1}{2}I_t^\gamma$ and hence after $\Oh(\ln\ln n)$ rounds the phase ends. For a complete proof see the following lemma. \begin{lem}\label{lem8} With probability $1-o(1)$, $T_1=\Oh(\ln\ln n)$. \end{lem} \begin{proof} At first we only consider {\sf Push} calls and apply Lemma \ref{push0} which states that as long as $S_t\leq \ln ^{\frac{2}{3-\beta}}n$, with probability $1-\Oh({\frac{\ln^{\frac{4}{3-\beta}} n}{n}})$, \begin{align*} I_{t+1}&=I_t+S_t\geq 2I_t. \end{align*} Thus as long as $S_t\leq \ln ^{\frac{2}{3-\beta}}n$, in each round the number of informed nodes is at least doubled. So we conclude that with probability $1-o(1)$, $\Oh(\ln\ln n)$ rounds are sufficient to inform $\ln ^{\frac{2}{3-\beta}} n $ nodes. Let $T_0$ be the first round when $I_{T_0}\geq \ln ^{\frac{2}{3-\beta}} n$. %Using Lemma \ref{push1} implies that with probability $1-o(1)$, $T_0=\Oh(\ln\ln n)$. Let us define the constant $\gamma:=\frac{3-\beta}{2(\beta-2)}>0$. Let $T$ be the first round such that \[ I_{T-1}^{(1+\gamma)}\leq n^{\frac{1}{\beta-1}}/\ln n < I_{T}^{(1+\gamma)}. \] Now for any $T_0 \leq t \leq T$, we can apply Proposition \ref{bionom} and conclude that with probability $1-o(\frac{1}{n})$, \begin{align}\label{size} \sum_{u\in \mathcal{L}(I_t^{1+\gamma})}C_u\geq L(I_t^{1+\gamma})\cdot I_t^{1+\gamma}\geq \frac{n\cdot c_1\cdot I_t^{(1+\gamma)({2-\beta)}}}{2}. \end{align} So, \[ \frac{I_t}{n}\sum_{u\in \mathcal{L}(I_t^{1+\gamma})}C_u\geq \frac{ c_1\cdot I_t^{1+(1+\gamma)({2-\beta)}}}{2}= \frac{ c_1\cdot I_t^{3-\beta+\gamma({2-\beta)}}}{2}. \] %If in round $t$ a node $u \in \mathcal{L}(I_t^{1+\gamma})$ knows the rumor, then $S_{t+1}\geq I_t^{1+\gamma}$. So We will bound the probability that none of $u \in \mathcal{L}(I_t^{1+\gamma})$ gets informed by {\sf Pull} calls in round $t+1$ as follows, \begin{align*} \prod_{u\in \mathcal{L}(I_t^{1+\gamma})}\left(1-\frac{I_t}{n}\right)^{C_u}&=\left(1-\frac{I_t}{n}\right)^{\sum_{u\in \mathcal{L}(I_t^{1+\gamma})}C_u}\leq e^{-c_1\cdot I_t^{3-\beta+\gamma(2-\beta)}}=e^{-c_1\cdot I_t^{\frac{3-\beta}{2}}}. %&e^{-\Oh( {\log^{\alpha\frac{3-\beta}{2}}n})}\\ %&=o(1/n). \end{align*} Since for any $t\geq T_0$, $I_t\geq \ln ^{\frac{2}{3-\beta}} n $, we have that with probability at least $1- n^{-c_1}$, at least one node in $\mathcal{L}(I_t^{1+\gamma})$ gets informed by {\sf Pull} in round $t+1$. Hence we have that \[ S_{t+1} \geq I_t^{1+\gamma}. \] Let us now consider the {\sf Push} calls in round $t+2$. By applying Lemma \ref{push0} we know that as long as $S_{t+1}=o(n)$ with probability $1-o(\frac{1}{\ln n})$, \[ S_{t+1}(1-o(1))\leq N_{t+1}. \] Thus, \[ I_{t+2}\geq I_{t+1}+S_{t+1}(1-o(1))>\frac{I_t^{1+\gamma}}{2}. \] An inductive argument shows that for any integer $k\geq 1$ as long as $I_{T_0+2k-2}^{1+\gamma}\leq n^{\frac{1}{\beta-1}}/\ln n $, with probability $1-o(\frac{k}{\ln n})$ \[ I_{{T_0}+2k}>\left(\frac{1}{2}\right)^{\sum_{i=0}^{k-1}(1+\gamma)^i}I_{T_0}^{(1+\gamma)^k}= \left(\frac{I_{T_0}}{2^{\gamma}}\right)^{(1+\gamma)^k}\cdot 2^{1/\gamma}> \left(\frac{\ln^{\frac{2}{3-\beta}} n}{C'}\right)^{(1+\gamma)^k}, \] where $C'=2^{\gamma}=\Oh(1)$. So we conclude that after $T_0+2k$ rounds, where $k=o(\log_{1+\gamma}\ln n)$, there are two cases: either $I_{T_0+2k}\geq n^{\frac{1}{\beta-1}}/(2\ln n)$ which means $T_1\leq T_0+2k=\Oh(\ln\ln n)$ and we are done, or \[ I_{T_0+2k}< n^{\frac{1}{\beta-1}}/(2\ln n)\frac{3}{4}L(Z_{t+1})$. In the latter case, we define \[ \mathcal{L}'(Z_{t+1}):= \mathcal{L}(Z_{t+1})\cap \mathcal{U}_{t+1}. \] %And also we have that that $|\mathcal{L}'(Z_t)|>\frac{3}{4}L(Z_t)$. Let $X_u$ be an indicator random variable for every $u\in \mathcal{L}'(Z_{t+1})$ so that \[ X_u:= \left\{ \begin{array}{l l} 1 & \quad \text{if $u$ gets informed by {\sf Pull} in round $t+1$, }\\ 0 & \quad \text{otherwise.}\\ \end{array} \right. \] Then we define a random variable $X$ to be $ X:=\sum_{u\in \mathcal{L}'(Z_{t+1})}X_u. %\leq|\mathcal{L}(Z_{t+1})\cap \mathcal{U}_{t+1}|. $ Since for every $u\in \mathcal{L}'(Z_{t+1})$, $C_u\geq Z_{t+1} = \frac{n \log \log n}{I_t}$, it follows that \begin{align*} \Pr{X_u=1 }&=1-\left(1-\frac{I_t}{n}\right)^{C_u} \geq 1-\left(1-\frac{I_t}{n}\right)^{Z_{t+1}} =1-e^{-\Omega(\ln\ln n)}=1-o(1). \end{align*} Thus $\Pr{X_u=1 }>\frac{3}{4}$ and $\Ex{X}=\sum_{u\in\mathcal{L}'(Z_{t+1})}\Pr{X_u=1}>\frac{3}{4}|\mathcal{L}'(Z_{t+1})|.$ %We know that %\[ %L(Z_t)=|\mathcal {L}'(Z_t)|+|\mathcal{L}(Z_t)\cap \mathcal{I}_{t+1}|< |\mathcal {L}'(Z_t)| +\frac{1}{4}L(Z_t). %\] %So, %\[ %|\mathcal{L}'(Z_t)|>\frac{3}{4}|\mathcal{L}(Z_t)|. %\] Since \[ |\mathcal{L}'(Z_{t+1})|=|\mathcal{L}(Z_{t+1})\cap \mathcal{U}_{t+1}|>\frac{3}{4}L(Z_{t+1}),\] it follows that % added by CSG \[ \Ex{X}\geq \frac{9}{16}L(Z_{t+1}). \] We know that $I_t\geq {n^{\frac{1}{\beta-1}}}/{(2\ln n)}$ and also $I_t$ is a non-decreasing function in $t$, so \[ Z_{t+1}= \frac{n\ln\ln n}{I_t}\leq 2\cdot n^{\frac{\beta-2}{\beta-1}}\ln n\ln\ln n <{ n^{\frac{1}{\beta-1}}}/{\ln n}, \] where the last inequality holds because $\beta<3$. % with probability $1-o(\frac{1}{n})$, $L(Z_t)|$ is at least $\Omega(\ln^{\beta-1} n)$ for any $t$. Now we can apply Proposition \ref{bionom} (see appendix) to infer that with probability $1-o(\frac{1}{n})$, \[ {L}(Z_{t+1})\geq \frac{ n\cdot c_1\cdot Z_{t+1}^{1-\beta}}{2}\geq \frac{c_1\cdot \ln ^{\beta-1}n}{2}. \] Therefore, \[ \Ex{X}\geq \frac{9\cdot c_1\cdot \ln ^{\beta-1}n}{32}. \] Then applying Theorem \ref{DP09} results into \begin{align}\label{equ1} \Pr{X<\frac{\Ex{X}}{2}}\leq\Pr{|X-\Ex{X}|\geq \frac{\Ex{X}}{2}}<2e^{-\frac{\Ex{X}}{10}}\leq 2e^{-\Omega(\ln ^{\beta-1} n)}. \end{align} %In the following we find a lower bound for $L(Z_t)$. , upper bound in inequality (\ref{equ1}) becomes $o(\frac{1}{n})$. So with probability $1-o(\frac{1}{n})$, we have that \begin{align*} |\mathcal{L}(Z_{t+1})\cap \mathcal{I}_{t+1}|\geq X\geq \frac{\Ex{X}}{2} > \frac{3|\mathcal{L'}(Z_{t+1})|}{8} \geq\frac{1}{4}{L}(Z_{t+1}), \end{align*} where the last inequality holds because $|\mathcal{L}'(Z_{t+1})|>\frac{3}{4}L(Z_{t+1})$. \end{proof} \begin{lem}\label{nonactive} With probability $1-o(1)$, $T_2-T_1=\Oh(\ln\ln n)$. %If $I_t\geq n^{\frac{1}{\beta-1}}\ln^{-1}n$ and $I_t=o(n)$. Then with probability $1-o(1)$, after at most $\Oh(\log_{\frac{1}{\beta-2}}\ln n)$ rounds the number of uninformed nodes drops by $\Oh(\frac{n}{\ln\ln n})$. \end{lem} \begin{proof} Since $I_t\geq n^{\frac{1}{\beta-1}}/(2\ln n)$, $Z_{t+1}=\frac{n\ln\ln n}{I_t} \frac{S_{t+1}}{2} \geq\frac{c_1}{16}n\cdot Z^{2-\beta}_{t+1}=\frac{c_1}{16}\cdot n^{3-\beta}\cdot \ln\ln^{2-\beta} n \cdot I^{\beta-2}_t. \end{align*} By an inductive argument, we obtain that for any integer $k\geq 1$ with $S_{t+k}=o(n)$, it holds with probability $1-o(\frac{k}{\ln n})$, \begin{align*} I_{t+2k}&>\left(\frac{c}{16}n^{3-\beta}\cdot \ln\ln^{2-\beta} n\right)^{\sum_{i=0}^{k-1}(\beta-2)^i} I_t^{(\beta-2)^k} = \left(\frac{c}{16}n^{3-\beta}\cdot \ln\ln^{2-\beta} n\right)^{\frac{1-(\beta-2)^k}{3-\beta}}I_t^{(\beta-2)^k}. \end{align*} Therefore there exists $k=\Oh(\log_{\frac{1}{\beta-2}}\ln n)$ such that \begin{align*} I_{t+2k}&\geq \left(\frac{c}{16}n^{3-\beta}\cdot \ln\ln^{2-\beta} n\right)^{\frac{1-\Oh(1/\ln n)}{3-\beta}}I_t^{1/\ln n}\\ &=\Omega \left(n^{1-\Oh(1/\ln n)}\left(\frac{c}{16}\cdot \ln\ln^{2-\beta} n\right)^{\frac{1-\Oh(1/\ln n)}{3-\beta}}\right) =\Omega\left(\frac{n}{\ln \ln^{\delta} n}\right), \end{align*} where $\delta=\frac{\beta-2}{3-\beta}(1-\Oh(1/\ln n)) > 0$. Hence $T_2 \leq T_1 + 2k = T_1 + \Oh(\log \log n)$ with probability $1-o(1)$. \end{proof} %This phase starts with $I_t\geq n^{\frac{1}{\beta-1}}/(2\cdot\ln n)$ and ends when $U_t\leq \frac{n}{\ln\ln n}$. We define $Z_t=\frac{n\ln\ln n}{I_t}$. Note that $Z_t$ is non-increasing in %$t$ and upper bounded by $n^{\frac{1}{\beta-1}}/\ln n$. We prove that in round $t+1$ a constant fraction, say $1/4$, of $L(Z_t)$ knows the rumor. So $S_{t+1}\geq 1/4\cdot L(Z_t)\cdot %Z_t$ and applying Proposition \ref{bionom} results into a lower bound for %$L(Z_t)$. So we infer that $S_{t+1}\geq c\cdot n^{3-\beta}\ln\ln^{2-\beta} n\cdot I_t^{\beta-2}$, where $c=\Oh(1)$. As long as $S_t=o(n)$ we can apply %Lemma \ref{push3} and we have $I_{t+2}\geq \frac{S_{t+1}}{2}$. So an inductive argument shows that with probability $1-o(\frac{k}{\ln n})$ %after $k=\Oh(\ln\ln n)$ rounds the number of informed nodes increases to at least $\frac{n}{\ln n}$. %Now the probability that a node in $\mathcal{U}_t$ does not get informed by {\sf Pull} after $T$ rounds is bounded by $e^{\frac{-T}{\ln\ln\ln n}}$. Thus by taking $T=(\ln\ln\ln n)^3$ the number of uninformed nodes drops by a factor of $\frac{1}{\ln\ln^2 n}$ and using Markov's inequality implies that $U_t$ decreases to $\frac{n}{\ln\ln n}$ with probability $1-o(1)$. %\paragraph{The Final Phase.} \subsubsection*{The Final Phase.} This phase starts with at least $\frac{n}{\ln n}$ informed nodes. Since the runtime of our {\sf Push-Pull} protocol is stochastically smaller than the runtime of the standard {\sf Push-Pull} protocol (i.e. $C_u=1$ for every $u \in V$), we simply use the result by Karp et.~al in \cite[Theorem~2.1]{KSSV00} for the standard {\sf Push-Pull} protocol which states that once $I_t\geq\frac{n}{\ln n}$, additional $\Oh(\ln\ln n)$ rounds are with probability $1-o(1)$ sufficient to inform all $n$ nodes. \qed \subsection{Proof of the Lower Bound}\label{lowerbound} %\begin{lem} %Assume that $R$ is a power law distribution with $2 <\beta< 3$. Then the {\sf Push-Pull} protocol %needs at lest $\Omega(\log \log n)$ rounds to inform all nodes with probability $1 - o(1)$. % \end{lem} % \begin{proof} Since increasing the number of informed nodes can only decrease the runtime of the protocol, we may assume that at the beginning there are $\log ^{b}n$ random informed nodes, where $b:=\max\{4, 2+ \frac{3(3-\beta)}{\beta-2}\}$. Applying Markov's inequality to the random variable $S_0$ implies that with probability $1-o(\frac{1}{\log n})$, $\log ^{b}n\leq S_0 \leq \log ^{2+b}n$. In the following we lower bound the number of rounds to reach $n^{\frac{1}{\log\log n}}$ informed nodes. We do this by keeping track of the largest value of $C_u$ among all informed nodes and show that this value does not exceed $I_t^{\frac{1}{\beta-2}}\log^{\frac{3}{\beta-2}} n$ with high probability. %Since the $C_u$'s are generated according to a power law distribution, $\Pr{C_u\geq n^{\frac{1}{\beta-1}}\log n } \leq \frac{1}{n\cdot \log^{\beta-1} n}$ and applying the union bound implies that %with probability $1-o(\frac{1}{\log n})$ we have $C_u\leq n^{\frac{1}{\beta-1}}\log n$ for every $u\in \mathcal{V}$. By Fact~\ref{fact}, with probability $1-o(\frac{1}{\log n})$ we have $\max_{u \in {\cal V}} C_u\leq n^{\frac{1}{\beta-1}}\log n$. Let $i^*$ be the smallest positive integer so that $2^{i^*}\geq n^{\frac{1}{\beta-1}}/ \ln n$. Then $i^*<\log n$. Let us define the set $\mathcal{M}_i:=\{u\in \mathcal{V} \colon 2^{i-1}\leq C_u < 2^i\}$ for $1\leq i\leq i^*-1$ and $\mathcal{M}_{i^*}:=\{u\in \mathcal{V} \colon 2^{i^*-1}\leq C_u\leq n^{\frac{1}{\beta-1}}\log n \}$. We denote the size of $\mathcal{M}_i$ with $M_i$. By definition, for any $1\leq i\leq i^*$, $M_i\leq L(2^{i-1})$. Applying Proposition \ref{bionom} implies that with probability $1-o(\frac{1}{n})$ for any $1\leq i\leq i^*$ we have $M_i\leq \frac{3}{2}\cdot c_2\cdot n\cdot 2^{(i-1)(1-\beta)}$. Let us define the indicator random variable $Z^i_u$ for every $u\in \mathcal{U}_t\cap\mathcal{M}_i$ as follows: \[ Z^i_u:= \left\{ \begin{array}{l l} 1 & \quad \text{if $u$ gets informed by {\sf Pull} in round t+1, }\\ 0 & \quad \text{otherwise.}\\ \end{array} \right. \] Hence, $\Pr{Z_u^i=1}\leq C_u \cdot \frac{I_t}{n} \leq \frac{I_t\cdot2^i}{n}$. Let $P_i$ be the probability that at least one node in $\mathcal{U}_t\cap \mathcal{M}_i$ gets informed by {\sf Pull} in round $t+1$. Then, for any $1\leq i\leq i^*-1$, \[ P_i\leq\sum_{u\in \mathcal{U}_t\cap \mathcal{M}_i}\Pr{Z_u^i=1}\leq M_i \cdot \frac{I_t}{n}\cdot 2^{i}\leq 3\cdot c_2\cdot I_t\cdot 2^{(i-1)(2-\beta)}. \] Since $2^{i^*}\geq{n^{\frac{1}{\beta-1}}}/{\log n}$ and $C_u\leq n^{\frac{1}{\beta-1}}\log n$ with probability $1-o(\frac{1}{\log n})$, \begin{align*} P_{i^*}\leq\sum_{u\in \mathcal{U}_t\cap \mathcal{M}_{i^*}}\Pr{Z_u^i=1} &\leq \frac{3}{2}\cdot c_2 \cdot n\cdot2^{(i^*-1)(1-\beta)} \cdot \frac{I_t}{n}\cdot n^{\frac{1}{\beta-1}}\log n \\ &\leq 6\cdot c_2\cdot {I_t}\cdot n^{\frac{2-\beta}{\beta-1}}\log^{\beta-1}\cdot n. \end{align*} So as long as $I_t\leq n^{\frac{1}{\log\log n}}$, $P_{i^*}=o(\frac{1}{\log^3 n})$. We define $\Delta_t:=S_t^{\frac{1}{\beta-2}}\log^{\frac{3}{\beta-2}} n$. Let $1\leq i_t\leq i^*$ be the smallest integer so that $2^{i_t}\geq \Delta_t$. Then for any $i_t \leq i\leq i^*$ we have, \[ P_i\leq 3\cdot c_2\cdot 2^{\beta-2}\cdot I_t\cdot 2^{i(2-\beta)}\leq 6\cdot c_2\cdot I_t \cdot\Delta_t^{2-\beta}\leq 6\cdot c_2\cdot \log^{-3}n. \] Let $E_t$ be the event that no node with $C_u\geq \Delta_t$ gets informed by {\sf Pull} in round $t+1$. Then we have \begin{align}\label{event} \Pr{E_t}\geq1-\sum_{i=i_t}^{i^*}P_i\geq 1-o\left(\frac{1}{\log n}\right). \end{align} % % Let us define event $E:=\cap_{t=0}^{\log\log n}E_t\cap A$. %Using the union bound for the event $\bar{E}$ yields that with probability $\Pr{\bar{E}}\leq o(\frac{\log\log n}{\log n})$. So we have $\Pr{E}\geq 1-o(\frac{\log\log n}{\log n})$.} %no node $u$ with $C_u\geq \Delta_t$ gets informed by {\sf Pull} in round $t+1$. %For every $u\in \mathcal{U}_t$, we define $A_u$ to be the event that $\{C_u\leq \Delta_t \text{ and $u$ gets informed by {\sf Pull} in round } t+1\}$ and $A_t:=\cup_{u\in \mathcal{U}_t}A_u$. Then $\Pr{A_t}=1-o(\frac{1}{\log n})$. Let us define $S_{t+1}^{(1)}:=\sum_{u\in \mathcal{N}^{{\sf Pull}}_t}C_u$. Conditioning on the event $E_t$ we obtain that %\NOTE{Thomas}{Shouldn't we drop the rightmost term after $\leq$ below? And in general, why are we dropping the conditioning on $S_t$ in $\Ex{S_{t+1}}$?}\NOTE{ali}{ because always I m saying this is conditional I dropped it for simplicity, may be It is better to say $S_t^{(1)}$ itself is a conditional random variable or we can add the condition symbol? } \begin{align*} \Ex{S_{t+1}^{(1)}~|~S_t}&\leq \sum_{i=1}^{i_t}\sum_{u\in \mathcal{U}_t\cap \mathcal{M}_i} C_u\cdot \frac{\Pr{Z_u^i=1}}{\Pr{E_t}} \\ &\leq (1+o(1))\cdot\sum_{i=1}^{i_t} 2^i \cdot M_i \cdot \frac{I_t}{n} \cdot 2^i\leq (1+o(1))\cdot \frac{S_t}{n}\cdot \sum_{i=1}^{i_t} 2^i \cdot M_i \cdot 2^i. \end{align*} % \red{where the last inequality holds, because for every $1\leq i\leq i_t$ we have $\Pr{Z_u^i=1, E_t ~|~ I_t} \leq \Pr{Z_u^i=1~|~I_t}\leq \frac{I_t}{n} \cdot 2^i$ and for every $i>i_t$, we have $\Pr{Z_u^i=1, E_t ~|~ I_t}=0$.} By definition of $i_t$, we have $2^{i_t}\leq 2\cdot\Delta_t$ and also we have $M_i\leq L(2^{i-1})\leq \frac{3}{2}\cdot c_2 \cdot2^{(i-1)(1-\beta)}\cdot n$. Hence the last sum is bounded by \begin{align*} (1+o(1))\cdot \sum_{i=1}^{i_t} 2^{2i} \cdot I_t \cdot 2^{(i-1)(1-\beta)} \leq 24\cdot c_2\cdot I_t\cdot 2^{i_t(3-\beta)} &\leq 24\cdot c_2\cdot I_t\cdot (2\cdot \Delta_t)^{3-\beta}\\ &\leq 24\cdot c_2 \cdot S_t^{1+\frac{3-\beta}{\beta-2}}\log^{\frac{3(3-\beta)}{\beta-2}} n. \end{align*} Conditioning on the event $E_t$ and applying Markov's inequality imply that with probability $1-o(\frac{1}{\log n})$, \begin{align}\label{pull} S^{(1)}_{t+1}\leq \log ^2n\cdot \Ex{S_{t+1}^{(1)}~|~S_t}\leq 24\cdot c_2 \cdot S_t^{1+\frac{3-\beta}{\beta-2}}\log^{2+\frac{3(3-\beta)}{\beta-2}} n. \end{align} Let us define the indicator random variable $Y_u$ for every $u\in \mathcal{U}_t$ as follows: \[ Y_u:= \left\{ \begin{array}{l l} 1 & \quad \text{if $u$ gets informed by {\sf Push} in round t+1, }\\ 0 & \quad \text{otherwise.}\\ \end{array} \right. \] Then we have $\Pr{Y_u=1}\leq {S_t}/{n}$. Let $A$ denote the event that $\sum_{u\in \mathcal{V}}C_u\leq n\cdot\log ^2n$. Since $\Ex{R}=\Oh(1)$, applying Markov's inequality implies that $\Pr{A}\geq1-o({1}/{\log n})$. Let us define $S_{t+1}^{(2)}:=\sum_{u\in \mathcal{N}^{{\sf Push}}_t}C_u$. Conditioning on the event $A$ we have \begin{align*} \Ex{S_{t+1}^{(2)}~|~S_t}=\sum_{u\in\mathcal{U}_t} C_u\cdot \frac{\Pr{Y_u=1}}{\Pr{A}}\leq (1+o(1))\cdot\sum_{u\in\mathcal{V}}C_u\cdot \frac{S_t}{n} \leq (1+o(1))\cdot S_t\cdot \log^2 n. \end{align*} Conditioning on $A$ and applying Markov's inequality implies that with probability $1-o({1}/{\log n})$, \begin{align}\label{push} S^{(2)}_{t+1}\leq \log ^2n\cdot \Ex{S_{t+1}^{(2)}~|~S_t}\leq S_t \cdot \log^4 n \end{align} %Recall that $b=\max\{2, \frac{3(3-\beta)}{\beta-2}\}$. %Conditioning on events $E_t$ and $A$, we Combining inequalities (\ref{pull}) and (\ref{push}) implies that with probability $1-o({1}/{\log n})$ for every $0\leq t\leq \log \log n$ %that there is a constant $\alpha>1$ so that \begin{align*} S_{t+1}\leq S_t +S_{t+1}^{(1)} + S_{t+1}^{(2)}& \leq S_t + 24\cdot c_2\cdot S_t^{1+\frac{3-\beta}{\beta-2}}\log^{2+\frac{3(3-\beta)}{\beta-2}} n + S_t\cdot \log^4 n\\ &\leq S_t + 24\cdot c_2\cdot S_t^{b+1} +S_t^2\leq S_t^{b+2}, \end{align*} where the last inequality holds because $b=\max\{4, 2+\frac{3(3-\beta)}{\beta-2} \}$ and $\log ^{b}n\leq I_t\leq S_t$. We know that with probability $1-o({1}/{\log n})$ we have $S_0\leq \log ^{b+2} n$. An inductive argument shows that for every $1\leq t\leq \log\log n$ with probability $1-o(1)$, $S_t\leq S_0^{(b+2)^t}\leq\log ^{(b+2)^{t+1}}$. If we set $T:= \frac{1}{2}\cdot \log_{b+2}\log n$, then with probability $1-o(1)$ we have $S_T < n^{{1}/{\log\log n}}$. Thus $T=\Omega(\log\log n)$ rounds are necessary to inform all nodes with probability $1-o(1)$. This finishes the proof of the lower bound of $\Omega(\log \log n)$. \qed % % \NOTE{Thomas}{Wouldn't it be more clearer here if we use Markov's inequality to show that $S_{t+1} \leq \Ex{S_{t+1} \, \mid \, S_{t}} \cdot \log^3 n$ with probability at least $1-1/\log^2 n$ and then take the union bound over all steps $0 \leq t \leq \log \log n$?}\NOTE{Ali}{ I did not get your point, how should we use Markov for $S_{t+1}$ and conditional expectation $\Ex{S_{t+1} | S_t}$?} % \NOTE{Thomas}{We define $\log \log n$ ``good events'' and if every good event (in combination with the previous good events) ensures that $S_{t+1}$ is not too large in comparison with $S_t$. % Otherwise it is tricky to compute the expectation, since there is all this conditioning.}\NOTE{ali}{I changed the proof} %\end{proof} \section{Push-Pull Protocol with Power Law Distribution $\beta=3$ }\label{sub:pushpullpowerlaw3} In this section we analyse the {\sf Push-Pull} protocol where $R$ is a power law distribution with $\beta=3$ and show that the {\sf Push-Pull} protocol takes $\Theta\left(\frac{\log n}{\log\log n}\right)$ rounds to inform all $n$ nodes. Throughout this section we assume that the power law distribution with $\beta=3$ has an additional property in which for every positive integer $z$ \begin{align}\label{equal1} \Pr{R=z}\geq {c} \cdot z^{-3}, \end{align} where $c > 0$ is fixed. %Suppose that $C_u$'s, $u\in \mathcal{V}$, are generated according to a power law distribution with $\beta=3$. Let us define $\mathcal{L}^*(z)=\{u : C_u=z\}$ and $L^*(z)=|\mathcal{L}^*(z)|$. Also we define $\mathcal{I}_t(z)=\mathcal{I}_t\cap\mathcal{L}^*(z)$ and $\mathcal{N}_t(z)=\mathcal{N}_t\cap\mathcal{L}^*(z)$, whose sizes are denoted by $I_t(z)$ and $N_{t}(z)$ respectively. $N_{t}^{\sf Push}(z)$ and $N_{t}^{\sf Pull}(z)$ are denoted the size of the newly informed nodes with $C_u=z$ by {\sf Push} and {\sf Pull} transmissions respectively. In the following we show a useful fact about the $L^*(z)$. \begin{fact}\label{equal2} Let $R$ be a power law distribution with $\beta=3$. Then for every $z=\Oh({n^{1/4}})$, with probability $1-o(\frac{1}{n})$ we have that \[ \frac{n\cdot \Pr{R=z}}{2} \leq L^*(z)\leq \frac{3\cdot n\cdot \Pr{R=z}}{2}. \] \end{fact} \begin{proof} We know that $\Ex{L^*(z)}=n\cdot\Pr{R=z}$. By using the inequality (\ref{equal1}) we have that for any $z=\Oh(n^{1/4})$, $\Pr{R=z}=\Omega(n^{-3/4})$. Then we have that $\Ex{L^*(z)}=\Omega (n^{2/5})$ and using a Chernoff bound \ref{DP09} yields that with probability $1-o(\frac{1}{n})$ the inequality in the statement holds. \end{proof} \subsection{ Proof of Lower Bound} \begin{thm} With probability $1-o(1)$, the {\sf Push-Pull} needs at least $\Omega\left(\frac{\log n}{\log\log n}\right)$ rounds to inform all $n$ nodes. \end{thm} \begin{proof} Let $\{C_u \colon u\in \mathcal{V}\}$ be a sequence of positive integers where every $C_u$ is generated independently according to a power law distribution with $\beta=3$. We call a sequence $\{C_u \colon u\in \mathcal{V}\}$ is good if it fulfills three conditions: \begin{enumerate} \item For every $u\in \mathcal{V}$, $C_u1-\frac{c_1}{n^2}=1-o(1). \] We know that $\Ex{R}=\Oh(1)$, so Markov'e inequality implies that with probability $1-\Oh(\frac{1}{\log n})$, $S_0=\Oh(\log n)$. Conditioning on the event that for every $u\in \mathcal{V}$, $C_u\frac{L^*(z)\cdot I_t\cdot z}{4\cdot n}\geq \frac{ I_t\cdot z\cdot \Pr{R=z}}{8}\geq\frac{c\cdot I_t}{I_t^{\frac{3}{4}}}, \end{align} where the last inequality holds because $ \Pr{R=z}\geq \frac{c}{z^{3}}$. Since $ I_t=e^{\Omega\left(\frac{\log n}{\log\log n}\right)}$ and $X_u$'s are independent, applying a Chernoff bound \ref{DP09} implies that with probability $1-o(\frac{1}{n})$, \[ X_t(z)\geq\frac{\Ex{X_t(z)}}{2}. \] Using the above inequality and inequality (\ref{inequal3}) shows that that with probability $1-o(\frac{1}{\log n})$ there exists a constant $C$ so that \[ S_{t+1}\geq \sum_{z=1}^{z_t}X_t(z)\cdot z\geq \frac{I_t}{16}\sum_{z=1}^{z_t} z^2\cdot\Pr{R=z}\geq\frac{c\cdot I_t}{16} \sum_{z=1}^{z_t} \frac{1}{z} =I_t\cdot C\cdot \log z_t. \] For any positive integer $k$ in which $I_{t+k}\in [\mathrm{e}^{\Omega\left(\frac{\log n}{\log\log n}\right)}, \mathrm{e}^{\log n-\frac{\log n}{ \log\log n}}]$, we have that \[ \mathrm{e}^{\Omega\left(\frac{\log n}{\log\log n}\right)}\leq z_t.\] Hence from the above inequality we conclude that here exists a constant $C_1$ so that \[ S_{t+1}\geq C_1\cdot I_t\cdot \frac{\log n}{\log\log n}\geq C_1\cdot I_t\cdot \sqrt{\log n}. \] Considering only Push transmission for $S_t=o(n)$ and applying Lemma \ref{push3} implies that with probability $1-o(\frac{1}{\log n})$ \[ I_{t+2}\geq \frac{S_{t+1}}{2}\geq \frac{C_1\cdot I_t\cdot \sqrt{\log n}}{2} \] An inductive argument shows that for any integer $k$ as long as $S_{t+2k}=\frac{n}{\log^6 n}$ with probability $1-o(1)$, \[ I_{t+2k}\geq I_t\cdot \left(\frac{C_1\cdot \sqrt{\log n}}{2}\right)^k. \] Thus there is a $k=\Oh\left(\frac{\log n}{\log\log n}\right)$ so that after $t+2k$ rounds there are at least $\mathrm{e}^{\log n-\frac{\log n}{\log\log n}}$ informed nodes. \end{proof} \begin{cor} let $R$ be a power law distribution with $\beta=3$. Then with probability $1-o(1)$, the {\sf Push-Pull} protocol in informs all $n$ nodes in $\Oh\left(\frac{\log n}{\ln\ln n}\right)$ rounds. \end{cor} \begin{proof} Applying Corollary \ref{exponential} results that as long as $S_t=o(n)$ with probability $1-o({1})$, for any round $t=\Oh(\log n)$, \begin{align*} I_{t}\geq \left(\frac{3}{2}\right)^t\cdot I_0. \end{align*} So after $\Oh\left(\frac{\log n}{\log\log n}\right)$ rounds there are at least $\mathrm{e}^{\Omega\left(\frac{\log n}{\log\log n} \right)}$ informed nodes. Now we apply Lemma \ref{mainphase} and conclude that after $\Oh\left(\frac{\log n}{\log\log n}\right)$ rounds we have at least $\mathrm{e}^{\log n-\frac{\log n}{\log\log n}}$ informed nodes. Another application of Corrolarry \ref{exponential} implies that after $\Oh(\frac{\log n}{\log\log n})$ rounds we have at least $\frac{n}{\log\log n}$ informed nodes. Since we have enough number of informed nodes using the result by Karp et.~al in \cite[Theorem~2.1]{KSSV00} for the standard {\sf Push-Pull} protocol shows that once $I_t\geq\frac{n}{\ln n}$, with probability $1-o(1)$ additional $\Oh(\ln\ln n)$ rounds are sufficient to inform all $n$ nodes. \end{proof} \section{Generating a New $C_u^t$ in Each Round (Theorem \ref{thm:generator})}\label{sec:newmodel} In this section we analaysis the {\sf Push-Pull} protocol for a new model. In this model according to some distribution $R$, at the beginning of each round $t$, every node $u$ generates a random natural number $C^t_u\geq 1$ independent of all other nodes. Then in round $t$, the {\sf Push-Pull} protocol disseminates the information according to $\{C_u^t \colon u \in \mathcal{V}\}$, i.e., node $u$ calls $C_u^t$ random nodes. In the following we show that if we have $\Ex{R}=\Oh(1)$. Then with probability $1-o(1)$, the {\sf Push-Pull} protocol needs $\Omega(\ln n)$ rounds to inform all nodes. \begin{proof} The probability that a node $u\in \mathcal{U}_t$ gets informed by {\sf Pull} is as follows: \begin{align*} &\quad\Pr{u \text{ gets informed by {\sf Pull} in round}~ t+1}\\ &=\sum_{x=1}^{\infty}\Pr{u\text{ gets informed by {\sf Pull} in round}~ t+1~|~R^{t+1}_u=x}\cdot\Pr{R^{t+1}_u=x}\\ %&=\sum_{x=1}^{\infty}\left(1-\left(1-\frac{I_t}{n}\right)^x\right)\Pr{R^{t+1}_u=x}\\ &=\sum_{x=1}^{\lfloor\frac{n}{2I_t}\rfloor} \left(1-\left(1-\frac{I_t}{n}\right)^x\right)\cdot\Pr{R^{t+1}_u=x}+\sum_{x=\lfloor\frac{n}{2I_t}\rfloor+1}^{\infty} \left(1-\left(1-\frac{I_t}{n}\right)^x\right)\cdot\Pr{R^{t+1}_u=x}\\ &\leq \frac{I_t}{n}\sum_{x=1}^{\lfloor\frac{n}{2I_t}\rfloor}x\cdot\Pr{R^{t+1}_u=x}+\sum_{x=\lfloor\frac{n}{2I_t}\rfloor+1}^{\infty} \Pr{R^{t+1}_u=x} \quad \left(\text{since $1-\left(1-\frac{I_t}{n}\right)^x\leq \frac{I_t\cdot x}{n}$}\right) \\ &\leq \frac{I_t}{n}\cdot\Ex{R}+\Pr{R^{t+1}_u>\left\lfloor\frac{n}{2I_t}\right\rfloor} \leq \frac{I_t}{n}\cdot\Ex{R}+\frac{2I_t}{n}\cdot\Ex{R}, \end{align*} where the last inequality is due to Markov's inequality. Recall that $N_{t}^{{\sf Pull}}$ and $N_{t}^{{\sf Push}}$ are the number of newly informed nodes by {\sf Pull} and {\sf Push} calls in round $t+1$ respectively. Hence, \begin{align*} \Ex{{N}_{t}^{{\sf Pull}}\,|\, {I}_{t}}&= \sum_{u\in \mathcal{U}_t}\Pr{u~ \text{gets informed by {\sf Pull} in round}~ t+1}\\ &\leq \frac{U_t\cdot I_t\cdot 3\cdot \Ex{R}}{n}< 3\cdot I_t\cdot\Ex{R}. \end{align*} Recall that $S_t$ is the number of {\sf Push} calls by informed nodes in round $t+1$. Therefore, $N_{t}^{{\sf Push}}\leq S_{t}$ and \[ \Ex{N_{t}^{{\sf Push}} ~|~ I_t}\leq \Ex{S_{t} ~| ~I_t}=\sum_{u\in I_t}\Ex{C_u^{t+1}}=I_t\cdot\Ex{R}. \] Hence, \[ \Ex{I_{t+1} ~|~ I_t} \leq I_t +\Ex{N_{t}^{{\sf Pull}} ~|~ I_t} + \Ex{N_{t}^{{\sf Push}} ~|~ I_t} \leq (1+4\cdot\Ex{R})\cdot I_t. \] By using the law of total expectation, we conclude that $\Ex{I_{t} }<(1+4\cdot\Ex{R})^t $. If we set $T=c\cdot \ln n$, where $c>0$ is a small constant, then \[ \Pr{I_T\geq \sqrt{n}}\leq\frac{\Ex{I_T}}{\sqrt{n}}\leq\frac{(1+4\cdot\Ex{R})^T}{\sqrt{n}}=o(1). \] So with probability $1-o(1)$, we need at least $c \cdot \ln n$ rounds to inform all nodes. \end{proof} \begin{thebibliography}{10} \bibitem{BEF08} P.~Berenbrink, R.~Els{\"a}sser, and T.~Friedetzky. \newblock Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. \newblock In {\em Proc.~27th Symp.\ Principles of Distributed Computing (PODC)}, pages 155--164, 2008. \bibitem{BBCS05} N.~Berger, C.~Borgs, J.~Chayes, and A.~Saberi. \newblock On the {S}pread of {V}iruses on the {I}nternet. \newblock In {\em Proc.~16th Symp.\ Discrete Algorithms (SODA)}, pages 301--310, 2005. \bibitem{Boyd2006} S.~Boyd, A.~Ghosh, B.~Prabhakar, and D.~Shah. \newblock Randomized gossip algorithms. \newblock {\em IEEE Transactions on Information Theory}, 52(6):2508--2530, 2006. \bibitem{HS10} K.~Censor-Hillel and H.~Shachnai. \newblock Partial information spreading with application to distributed maximum coverage. \newblock In {\em Proc.~29th Symp.\ Principles of Distributed Computing (PODC)}, pages 161--170, 2010. \bibitem{CLP09} F.~Chierichetti, S.~Lattanzi, and A.~Panconesi. \newblock Rumor spreading in social networks. \newblock In {\em Proc.~36th Intl.\ Coll.\ Automata, Languages and Programming (ICALP)}, pages 375--386, 2009. \bibitem{CLP10} F.~Chierichetti, S.~Lattanzi, and A.~Panconesi. \newblock Almost tight bounds for rumour spreading with conductance. \newblock In {\em Proc.~42nd Symp.\ Theory of Computing (STOC)}, pages 399--408, 2010. \bibitem{CPS13} A.~E.~F. Clementi, F.~Pasquale, and R.~Silvestri. \newblock Opportunistic manets: Mobility can make up for low transmission power. \newblock {\em IEEE/ACM Transaction on Networking}, 21(2):610--620, 2013. \bibitem{DGH+87} A.~Demers, D.~Greene, C.~Hauser, W.~Irish, J.~Larson, S.~Shenker, H.~Sturgis, D.~Swinehart, and D.~Terry. \newblock Epidemic algorithms for replicated database maintenance. \newblock In {\em Proc.~6th Symp.\ Principles of Distributed Computing (PODC)}, pages 1--12, 1987. \bibitem{DF11} B.~Doerr and M.~Fouz. \newblock Asymptotically optimal randomized rumor spreading. \newblock In {\em Proc.~38th Intl.\ Coll.\ Automata, Languages and Programming (ICALP)}, pages 502--513, 2011. \bibitem{DFF11} B.~Doerr, M.~Fouz, and T.~Friedrich. \newblock Social networks spread rumors in sublogarithmic time. \newblock In {\em Proc.~43th Symp.\ Theory of Computing (STOC)}, pages 21--30, 2011. \bibitem{DFF12} B.~Doerr, M.~Fouz, and T.~Friedrich. \newblock Asynchronous rumor spreading in preferential attachment graphs. \newblock In {\em Proc.~13th Scandinavian Workshop Algorithm Theory (SWAT)}, pages 307--315, 2012. \bibitem{DP09} D.~Dubhashi and A.~Panconesi. \newblock {\em Concentration of Measure for the Analysis of Randomized Algorithms}. \newblock Cambridge University Press, 2009. \bibitem{ES06} R.~Els{\"{a}}sser and T.~Sauerwald. \newblock On the runtime and robustness of randomized broadcasting. \newblock In {\em Proc. 17th Intl. Symp. Algorithms and Computation, {(ISAAC)}}, pages 349--358, 2006. \bibitem{ES08} R.~Els{\"a}sser and T.~Sauerwald. \newblock The power of memory in randomized broadcasting. \newblock In {\em Proc.~19th Symp.\ Discrete Algorithms (SODA)}, pages 218--227, 2008. \bibitem{FPRU90} U.~Feige, D.~Peleg, P.~Raghavan, and E.~Upfal. \newblock Randomized broadcast in networks. \newblock {\em Random Structures and Algorithms}, 1(4):447--460, 1990. \bibitem{FHP10} N.~Fountoulakis, A.~Huber, and K.~Panagiotou. \newblock Reliable broadcasting in random networks and the effect of density. \newblock In {\em Proc.~29th IEEE Conf.\ Computer Communications (INFOCOM)}, pages 2552--2560, 2010. \bibitem{FP10} N.~Fountoulakis and K.~Panagiotou. \newblock Rumor spreading on random regular graphs and expanders. \newblock In {\em Proc.~14th Intl.\ Workshop on Randomization and Comput.\ (RANDOM)}, pages 560--573, 2010. \bibitem{FPS12} N.~Fountoulakis, K.~Panagiotou, and T.~Sauerwald. \newblock Ultra-fast rumor spreading in social networks. \newblock In {\em Proc.~23th Symp.\ Discrete Algorithms (SODA)}, pages 1642--1660, 2012. \bibitem{FG85} A.~Frieze and G.~Grimmett. \newblock The shortest-path problem for graphs with random-arc-lengths. \newblock {\em Discrete Applied Mathematics}, 10:57--77, 1985. \bibitem{G11} G.~Giakkoupis. \newblock Tight bounds for rumor spreading in graphs of a given conductance. \newblock In {\em Proc.~28th Symp.\ Theoretical Aspects of Computer Science (STACS)}, pages 57--68, 2011. \bibitem{G13} G.~Giakkoupis. \newblock Tight bounds for rumor spreading with vertex expansion. \newblock {\em CoRR}, abs/1302.6243, 2013. \bibitem{GS12} G.~Giakkoupis and T.~Sauerwald. \newblock Rumor spreading and vertex expansion. \newblock In {\em Proc.~23th Symp.\ Discrete Algorithms (SODA)}, pages 1623--1641, 2012. \bibitem{Harchol-Balter1999} M.~Harchol-Balter, F.~T. Leighton, and D.~Lewin. \newblock Resource discovery in distributed networks. \newblock In {\em Proc.~18th Symp.\ Principles of Distributed Computing (PODC)}, pages 229--237, 1999. \bibitem{KSSV00} R.~Karp, C.~Schindelhauer, S.~Shenker, and B.~V\"ocking. \newblock Randomized {R}umor {S}preading. \newblock In {\em Proc.~41st Symp.\ Foundations of Computer Science (FOCS)}, pages 565--574, 2000. \bibitem{KDG03} D.~Kempe, A.~Dobra, and J.~Gehrke. \newblock Gossip-based computation of aggregate information. \newblock In {\em Proc.~44th Symp.\ Foundations of Computer Science (FOCS)}, pages 482--491, 2003. \bibitem{McD98} C.~McDiarmid. \newblock Concentration. \newblock In M.~Habib, C.~McDiarmid, J.~Ramirez-Alfonsin, and B.~Reed, editors, {\em Probabilistic Methods for Algorithmic Discrete Mathematics}, pages 195--243. Springer-Verlag, 1998. \bibitem{MS08} D.~Mosk-Aoyama and D.~Shah. \newblock Fast distributed algorithms for computing separable functions. \newblock {\em IEEE Transactions on Information Theory}, 54(7):2997--3007, 2008. \bibitem{PSSS11} Y.~Peres, A.~Sinclair, P.~Sousi, and A.~Stauffer. \newblock Mobile geometric graphs: Detection, coverage and percolation. \newblock In {\em Proc.~22nd Symp.\ Discrete Algorithms (SODA)}, pages 412--428, 2011. \bibitem{Pit87} B.~Pittel. \newblock On spreading a rumor. \newblock {\em SIAM Journal on Applied Mathematics}, 47(1):213--223, 1987. \bibitem{Renesse1998} R.~van Renesse, Y.~Minsky, and M.~Hayden. \newblock A gossip-style failure detection service. \newblock In {\em Proc. 15th IFIP Intl. Conf. Distributed Systems Platforms (Middleware'98)}, pages 55--70, 1998. \end{thebibliography} \end{document}