Threshold-Driven Streaming Graph: Expansion and Rumor Spreading

We aim to analyze a dynamic graph model that simultaneously captures two key features of modern peer-to-peer networks: a local threshold mechanism that bounds the degree of each vertex, and a node-churn process that regulates how vertices join and leave the network in each round. We kept all other modeling choices as simple and natural as possible, using the fewest parameters necessary. While this setting does not capture all aspects of real dynamic networks (such as the Bitcoin one), we believe that this approach can still recover qualitative properties and phenomena yielded by the simultaneous presence of the two features above, and that it can be robust to variations or extensions of the model’s complexity.

We introduce the Threshold-driven Streaming Graph model, abbreviated as $𝒯𝒮𝒢(n,d,c)$, which is obtained by combining the two processes described above: (i) the streaming node-churn model [13, 19], and (ii) the original raes protocol in [11] (see Definition 4 and Definition 5 for its formal definition). We first notice that, in every round $t⩾0$, the degree of each vertex $v$ is always bounded by the threshold $(c+1)d$: in particular, at most $d$ edges are generated by the requests sent by $v$ and at most $cd$ edges are due to the online requests received by $v$.

Consistently with other models of dynamic graphs with node churn [7, 6, 33, 38], we assume the presence of a link manager to apply the raes’s connection-request strategy: any vertex that makes a link request can access this entity and get a random destination vertex. Importantly enough, the role of the link manager we assume here is minimal: vertices cannot get any further information from it.⁶⁶6For instance, one vertex might ask the current degree of the selected destination or, even more, information about the current topology: this is not allowed. As we will elaborate later in this section, the total number of calls each vertex performs to the link manager is a key performance measure of the system and the raes’s strategy optimizes it.

As we will discuss later in Section 2, the $𝒯𝒮𝒢(n,d,c)$ model yields a complex stochastic process of graph snapshots $𝒢=\{G_t=(V_t,E_t):t\in \mathbb{N}\}$, where edges in $E_t$ are neither uniformly distributed nor mutually independent. Hence, the analysis of the key aspects, such as the expansion properties of the graph snapshots, requires coping with new technical issues that are likely to emerge in other, more realistic models as well.

Even though the node churn and the raes rules are simple in themselves, their combination, yielding the $𝒯𝒮𝒢$ dynamic graph, turns out to be rather complex, essentially because it generates both a non-uniform link distribution and induces subtle correlations between the links of every snapshot of the dynamic graph. Informally, on the one hand older vertices tend to have a higher degree than younger ones. On the other hand, the fact that connection requests might create conflicts with other requests and get rejected several times along their life generates non trivial correlations among the links that are active in a given graph snapshot, even if they have been established in different previous rounds.

Our analysis solves the above technical challenges and essentially limits the maximum (i.e. worst-case) correlation lying among any subset of links of the same snapshot (see Section 2 for an overview of this key technical part). We then use such limited correlation among edges to prove that the $𝒯𝒮𝒢(n,d,c)$ model generates graph snapshots having the following good expansion properties.

We observe that the above result is tight in the following sense. It is easy to see that a new incoming vertex may stay isolated for the first $o(\log n)$ rounds of its life with non negligible probability: then, it is clear that, at any round, there may be some vertex subset of $o(\log n)$ size having bad expansion.

Rumor Spreading refers to a class of simple epidemic protocols that, given a source vertex $s$ holding a piece of information (i.e. the rumor), aim to broadcast this information to all vertices of the graph. The basic, popular randomized variants of rumor spreading are the (synchronous) uniform push protocol and the pull protocol: in the former, at each round every informed node (i.e., every node that learned the rumor in a previous round) chooses a neighbor uniformly at random and sends the rumor to it. In pull, at each round, every uninformed node chooses a random neighbor; if that neighbor is informed, it sends the rumor to the uninformed node. Finally, the push-pull protocol combines both strategies above to inform new, uninformed nodes.

push and pull protocols have been shown to be effective in many networks applications [23, 34, 44], and, very importantly for our setting, they have been proved to be fault-tolerant [27, 28] and efficient even in some model of evolving graphs [16, 17, 26, 30]. A key question concerns the completion time, i.e., how many rounds such protocols take to broadcast the source information to all nodes in the graph [15, 37].

While flooding has been analyzed even on dynamic graphs that include node-churn [6, 13], to the best of our knowledge, no analytical results are known for any rumor-spreading protocol. As a further contribution, we study the completion time of the uniform push and pull over the $𝒯𝒮𝒢$ model and, exploiting Theorem 1, we prove the following bound.

Also the result of Corollary 2 is tight for the same reasons of Theorem 1: with non-negligible probability a new incoming vertex may stay isolated for the first $o(\log n)$ rounds and hence it cannot receive the source information. Then, it is clear that, at any round, there may be some subset of size $o(\log n)$ with vertices that are not informed.

Message-communication overhead is a crucial performance parameter in communication networks since it has a strong impact on node traffic congestion and on the time delay of fundamental tasks such as broadcast and consensus [1, 6, 22]. In the $𝒯𝒮𝒢(n,d,c)$ model the only messages exchanged by vertices are those determined by the pending link requests: the overall number of exchanged messages at every round $t$ is optimal in expectation and $O(\log n)$, w.h.p. Indeed, we prove that, at every round $t⩾0$, the overall number of calls to the link manager performed by the vertices in $V_t$ (i.e. the overall number of pending requests at round $t$) has constant expectation and is $O(\log n)$, w.h.p. We also show that the overall number of calls (i.e. the work) each vertex makes during all of its life has constant expectation and it is $O(\log n)$, w.h.p., as well. These results are easy consequences of Lemma 9 and Lemma 11.

We now introduce the key notions and quantities we will consider in the probabilistic analysis of the $𝒯𝒮𝒢(n,d,c)$ model.

A vertex with $cd$ incoming edges is called full and the set of full vertices at round $t$ is denoted as $B_t$. Each request at round $t$ is a pair $r=(v,i)$, where $v\in V_t$ is the vertex making the request and $i\in [d]$ is its index. For any vertex $v\in V_t$ (or any request $r\in V_t\times [d]$), we will denote with $t_v$ (resp. $t_r$) the first round in which $v$ (resp. $r$) appears in the dynamic graph. If a request $r$ is trying to connect to some vertex $u$, we say that $r$ targets the vertex $u$.

We observe that, at any round, there are pending requests. A connection request $r$ from a vertex $v$ is called pending at round $t$ if either $v$ has just joined the set of vertices $V_t$, or if $r$ has been rejected in round $t-1$, or if $r$ was connected at round $t-1$ to the node $u$ that leaves the network at round $t$. Such a request generates an edge in $E_t$ if and only if it is accepted by its target vertex at round $t$. Notice that, when a vertex joins the graph at time $t$, all its $d$ requests are pending at time $t$.

The queue at round $t$ is the random set $Q_t$ of all pending requests at round $t$. As we will see in the next sections, the queue plays a key role in our analysis. Moreover, by the definition of the $𝒯𝒮𝒢(n,d,c)$ model, the size $|Q_t|$ of the queue bounds the overall number of messages exchanged by the vertices at round $t$.

For any $t⩾1$ and any request $r\in V_t\times [d]$, the random variable $X_t(r)$ is defined as the destination of the request $r$ if $r$ is accepted (and thus generates an edge in $E_t$), while we set $X_t(r)=\mathrm{\varnothing }$ if the request $r$ was rejected at round $t$.

For any set $S$, denote with $r\stackrel{𝑡}{\to }S$ the event indicating that the request $r$ established a connection with a vertex in the set $S$ at round $t$: in other words, that the request $r$ is pending at round $t$, targets a vertex in the set $S$ and it is accepted.

Using a simple combinatorial argument, we next prove that the size of the set $B_t$ of full vertices (i.e. vertices with in-degree equal to $cd$) at round $t$ can never exceed a suitable threshold.

For each $t⩾1$, it holds $|E_t|⩽nd$, since each vertex has at most $d$ outgoing edges. Assume, by contradiction, that $|B_t|>\frac{n}{c}$. Then, since each vertex in $B_t$ has in-degree $cd$, this implies that $|E_t|⩾cd|B_t|>cd\cdot \frac{n}{c}=nd$, contradicting the fact that $|E_t|⩽nd$. $\mathrm{⊲}$

To analyze the expansion properties of the $𝒯𝒮𝒢$ snapshots, we show that the link requests from any subset of nodes are both nearly uniformly distributed across the entire node set and nearly mutually independent. This result is the main technical contribution of the paper and is formalized in the following

The full proof of the above lemma can be found in [5, Lemma 4.1], while here below we provide a short overview of its main ideas.

Consider the snapshot $G_t=(V_t,E_t)$ at round $t⩾2n$ and a set of link requests $R$. We want to control the probability that all requests in $R$ established a link to some set $P$ of vertices at round $t$. As a first step, we order the requests according to the last time they were accepted by some node of $P$. This way, we can telescopically condition the probability that a single request $r\in R$ establishes a link with $P$ at some time $s$ on an event involving only connections happened in the past. For $r$ to connect to $P$ at time $s$ two events must happen: $r$ has to be pending at time $s$ and the link manager has to point to some node of $P$ at time $s$. Since we are conditioning only on the past, the probability of the second event is uniform over all nodes present at time $s$. As a byproduct, we are left to show that the (conditional) probability that $r$ is pending at time $s$ is small enough. The conditioning forces us to go through a (painful) worst-case scenario analysis. The key idea is the following: during its life each request goes through cycles (called $W_0,W_1,\mathrm{\dots }$ in the proof) composed of two phases: a first phase where the request stays linked to a single vertex (until that vertex dies) and a second phase where the request is pending because it gets rejected before forming a new link. We show that, regardless of what happened in the past, the length of the first phase can be stochastically dominated from below by a suitable uniform random variable, while the length of the second phase can be stochastically dominated from above by a geometric random variable. The decomposition in cycles and the stochastic domination of the phases allow us to sandwich the event that $r$ is pending during its $f$-th cycle between two events, called $S_1(f)$ and $S_2(f)$. As $f$ varies, $S_1(f)$ and $S_2(f)$ form a partition of the space of events, allowing us to conclude. $◀$

As we observed in the previous section, the queue $Q_t$ (i.e. the set of all pending requests at round $t$) plays a crucial role in our probabilistic analysis. In particular, we will often exploit the following upper bound on its size.

The proof of the lemma can be found in [5, Lemma 4.2], while we here highlight one of its key-ingredients that has a per se interest: informally, whenever $Q_t$ reaches a logarithmic size, it will decrease by a constant factor, w.h.p.

The following lemma provides a bound on the overall number of rounds in which a fixed request $r$ is pending during all of its lifetime, namely on the quantity

The proof of the above lemma can be found in [5, Lemma 4.4].

Fix any subsets $S\subseteq V_t$ of size $\frac{n}{2000}⩽|S|⩽\frac{n}{2}$ and $T\subseteq V_t\setminus S$ such that $|T|=\lceil \frac{1}{10}|S|\rceil$ (from now on we will just suppose that $n/2000$ and $|S|/10$ are integers, for simplicity). Taking $P=S\cup T$ and $P^c=V_t\setminus P$, we have that

We note that for each $r\in S\times [d]$ it holds

where, calling $t_r⩽t$ the round when the request $r$ joined the graph, for any $A\subseteq V_t$

Indeed, if request $r$ established a connection with some vertex of $P^c$ when it entered the graph at time $t_r$, then it would still be connected to $P^c$ at time $t⩾t_r$. Note that it is possible that not all vertices of $P^c$ were already in the graph at time $t_r$.

For every vertex $a\in S$, consider now

the subset of vertices in $P^c\subseteq V_t$ that were in the graph when $a$ joined it. Clearly, $F_r(P^c)=F_r({𝒪}_{a(r)})$ if $r$ is a request from vertex $a(r)$. In the rest of the proof we will abbreviate $a(r)$ as $a$. Then, from (4) and (5) we have

Let $k=|S|$ and $\{a_1,\mathrm{\dots },a_k\}$ be an age-based ordering of the vertices in $S$ from the oldest to the youngest, so that . We will analyze the r.h.s. of (6) by subsequentially conditioning on the events involving older vertices. We start by writing

where we abbreviated ${𝒪}_{a_i}$ as ${𝒪}_i$ to ease the notation. Let us focus on the conditional probability in the last expression. Recall that any fixed $r\in \{a_k\}\times [d]$ may fail to establish a connection with ${𝒪}_k$ at time $t_r$ for two reasons: either because it targets a vertex outside of ${𝒪}_k$, or because it receives a rejection from the target vertex in ${𝒪}_k$. The first event occurs with probability $\frac{n-1-|{𝒪}_k|}{n-1}$ since the targets are chosen uniformly at random independently from the past. The second event happens if the targeted vertex is full at time $t_r$, or if the vertex targeted by $r$ is also targeted by too many other requests in $Q_{t_r}$. As we are interested in the rejection of the $d$ requests $\{(a_k,j),j\in [d]\}$, by the principle of deferred decision we can assume that all $r^{\prime }\in Q_{t_r}\setminus \{(a_k,j),j\in [d]\}$ are sent before $\{(a_k,j),j\in [d]\}$. Now, if any $r\in \{(a_k,j),j\in [d]\}$ targets a vertex that has an in-degree of at most $(c-1)d$ after all other requests in the queue are sent, the attempt will certainly be accepted, independently from the other $r^{\prime }\in \{(a_k,i),i\in [d]\}\setminus \{r\}$ and from what happened in the past. Therefore, if we call ${\tilde{B}}_{t_k}$ the set of vertices with load at least $(c-1)d$, at time $t_k$ and after all other requests in the queue are sent, the probability of $r$ being rejected is at most $\frac{|{𝒪}_k\cap {\tilde{B}}_{t_k}|}{n-1}$. Thus, we can conclude that

The same argument can be iteratively applied to $\mathrm{𝐏𝐫}\left[{\cap }_{i=1}^k{\cap }_{j=1}^d{F}_{(a_i,j)}({𝒪}_i)\right]$, isolating $d$ requests per iteration, and it leads to

where inequality $(I)$ follows since $1+x⩽{\mathrm{e}}^x$.

Now, if we look at the set of possible pairs $(a,b)\in S\times P^c$, two cases may arise:

1. (i)

   ,

2. (ii)

   $\left|\{(a,b)\in S\times P^c\mid {\mathrm{age}}_t(a)>{\mathrm{age}}_t(b)\}\right|⩾\frac{|S|\cdot |P^c|}{2}$.

If Case (i) holds, then

which implies that

Using the same argument of Claim 7, it can be shown that $|{\tilde{B}}_{t_a}|⩽\frac{n}{c-1}$, yielding

where in $(I)$ we used that $|S|⩽\frac{n}{2}$, that $|P^c|=n-\frac{11}{10}|S|$ and that we can take for example $c⩾16$ as in Lemma 13. By plugging (9) in (8), we obtain

Then, a union bound on all possible choices of $S,T$ leads us to $\mathrm{𝐏𝐫}\left[E_t\right]⩽{\mathrm{e}}^{-n}$, by using the fact that $s⩾\frac{n}{2000}$ and taking $d$ large enough.

The proof of Case (ii) can be completed with the same argument, by considering the requests sent from $P^c$ to $S$. $◀$

Fix $\beta =100{(cd)}^2$. To prove the lemma, we show that the following event holds w.h.p.

Notice that, in Lemma 13 and Lemma 14, we proved that all the sets $S\subseteq V_t$ with size at least $\beta \log n$ have vertex expansion at least $\frac{1}{10}$ w.h.p. Therefore, to show that $E$ holds w.h.p., we need to prove that there exists a subset $H_t\subseteq V_t$ such that, all the sets $S\subseteq H_t$ with $S⩽20\beta \log n$ have also vertex expansion at least $\frac{1}{20}$. Indeed, the fact that the subsets $|S|⩾\beta \log n$ have expansion at least $1/10$ implies directly that the event $E$ holds for such subsets, since, for each $S\subseteq H_t$ such that $|S|⩾20\beta \log n$, we have

In particular, we will take $H_t$ as all the set of nodes without pending requests at time $t$. More formally, we have that $E_1\cap E_2\cap E_3\subseteq E$, where $E_1$ and $E_2$ are the events defined in the Lemma 13 and Lemma 14, and

From Lemma 13 and Lemma 14, we have that $\mathrm{𝐏𝐫}\left[E_1^c\cup E_2^c\right]⩽4n^{-2}$. In what follows, we will show that $\mathrm{𝐏𝐫}\left[E_3^c\right]⩽2n^{-2}$.

Notice that, from Lemma 9, we have that, if $A=\{|Q_t|⩽\beta \log n\}$, it holds that

If we define ${\tilde{Q}}_t$ as the set of nodes $v\in V_t$ with at least one pending request, we have that $|{\tilde{Q}}_t|⩽|Q_t|$ and that (taking $H_t=V_t\setminus {\tilde{Q}}_t$)

Therefore, it holds that

where $(I)$ follows from Lemma 8, and $(II)$ from the fact that we are looking at $E_3^c\cap A$, hence $|{\tilde{Q}}_t|⩽\beta \log n$, and since $s⩽20\beta \log n$ and taking $d$ large enough.

From (11), since $\mathrm{𝐏𝐫}\left[E_1^c\cup E_2^c\right]⩽4n^{-2}$, and since $E_1\cap E_2\cap E_3\subseteq E$, it follows that

proving the lemma. $◀$

Our proof makes use of the following important result, that bounds the completion time of rumor spreading protocols over static graphs of bounded degree, and its proof argument (see [15, Theorem 12]). We recall its statement and provide a short overview of its proof argument.

Let us just consider the case where $\varphi =\mathrm{\Theta }(1)$. Let $I_t\subseteq V$ the set of informed nodes at round $t$ and assume that $|I_t|⩽n/2$. We first notice that, since $G$ is an almost-regular $\mathrm{\Theta }(1)$-expander, the size of the outer boundary of $I_t$ is such that $|\mathrm{\Gamma }(I_t)|⩾\gamma |I_t|$, for some constant $\gamma >0$. Then, at every round $t^{\prime }⩾t$, the pull or the push protocol let every node $v\in \mathrm{\Gamma }(I_t)$ to have constant probability to get informed. This implies that the expected number of informed nodes at round $t+1$ will be at least $(1+\mathrm{\Theta }(1))|I_t|$. By applying suitable concentration arguments, this fact is then used to show that, within $O(\log n)$ rounds, the number of informed nodes is at least $n/2$, w.h.p. Once the spreading process reaches at least $n/2$ informed nodes, the analysis proceeds in a similar way by looking at the set non-informed nodes at round $t$ and show that this quantity decreases at exponential rate, w.h.p. $◀$

In order to apply the above proof argument on the $𝒯𝒮𝒢$ model we need to cope with two main technical issues.

Our Lemma 13 shows that, at any round $t⩾2n$, each subset $S\subseteq V_t$ of the snapshot $G_t=(V_t,E_t)$ with $|S|⩾\beta \log n$ for some constant $\beta >0$, has conductance ${\varphi }_t(S)=\mathrm{\Omega }(1)$, w.h.p. Then, in order to apply the proof argument of Theorem 16, we need to show that there is an initial phase of the rumor-spreading process, called bootstrap, that is able to inform at least $\beta \log n$ vertices, w.h.p. Indeed, after this bootstrap, we can apply the same argument of the proof of Theorem 16 assuming that there is an informed subset of logarithmic size. The analysis of the bootstrap will be discussed later in this section.

The second technical issue is caused by the presence of a set of old nodes (defined later in this section) that, during the information process, can leave the graph and create edge deletions and regenerations. However, once the bootstrap is completed, the subset of informed nodes reaches a logarithmic size which is large enough to dominates the impact of all possible edge deletions that can take place for a time window of logarithmic size even in an adversarially fashion: this time window is exactly what the rumor spreading process needs to complete the broadcast task. As we used in several previous steps of our analysis, this limited impact is essentially due to the fact that the maximum vertex degree of the graph snapshots is always bounded by the constant quantity $(c+1)d$ and thus, at every round, only this number of edges can be deleted.

Recall that $s$ is the source node joining the dynamic graph in round $t_s⩾2n$. Let $\mathrm{OLD}$ be the nodes in $V_{t_s}$ having age larger than $n-{\log }^{2}n$. Our goal is to prove the following.