How Long Does It Take to Spread a Rumor?
Gossip Algorithms in Distributed Systems

• Familiarity with single-variable calculus, probability, and discrete math may be helpful for sections 2, 3, and 4. Familiarity with distributed systems may be helpful for section 5. These are suggestions, not prerequisites.

• You can navigate through the text with the L/R arrow keys or the arrows in the bottom left.

• Definitions, comments, and other supplementary information is contained in green boxes throughout the text.

• There are also several animations throughout the text. You can pause these with the “Toggle Animations” button.

We say a system is $\textit{distributed}$ if it runs on multiple servers that communicate by sending messages over a network. Although distributed systems can be challenging to program correctly, they can offer better performance and resiliency than single-node systems. In the background, many distributed systems use $\textbf{gossip algorithms}$ to coordinate sharing information quickly over large networks.

In a gossip algorithm, one node broadcasts an update to all other nodes through multiple rounds of point-to-point messaging. A node spreads an update by sending a message to (or “gossiping with”) a randomly selected neighbor once per round. In subsequent rounds, the selected node is “activated” and begins gossiping with its neighbors. We allow this process to continue until all nodes have received a message. For the remainder of our discussion, I’ll ignore many of the challenges associated with building real distributed systems and represent them as $\textit{undirected graphs}$.

$\textbf{Comment:}$ If you’re familiar with distributed systems you’ve likely heard of (or even used!) applications that run a variation of gossip. Notably, the distributed databases Riak, Apache Cassandra, and DynamoDB all use gossip algorithms for communicating cluster membership and node failure detection.

Consider a distributed database with nodes storing an identical set $\Big(\textbf{S})$. At any moment, any node may receive an update that modifies its copy of $\textbf{S}$. Following the update, the node stores a different set $\Big(\textbf{S}')$. Until this change is propagated to all nodes, those storing $\textbf{S}$ and those storing $\textbf{S}'$ will return different results for identical operations.

To understand the scope of this problem, we must understand the performance of the gossip algorithm. Its clear that the number of rounds ($R_g$) required for gossip to complete is random, but what can we say about its $\textit{distribution}$? In the following sections, we’ll calculate bounds on $R_g$ by studying undirected complete graphs. By the end of this discussion, we’ll have a general answer to the following question:

$\textbf{Comment}$: A real number $x$ is an upper bound of a set $\textbf{R}$ if $x \geq r$ for all $r \in \textbf{R}$. For our purposes, the $\textit{least upper bound}$ is the smallest demonstrable upper bound. A similar definition applies for the lower bound. For a given system, let $\textbf{R}$ represents the set of all values $R_g$ may take. We’ll focus on finding the least upper bound ($u_0$) and greatest lower bound ($l_0$) for this set.

As you’ll soon see, $R_g$ is $\textit{unbounded from above}$ so $u_0$ doesn’t exist. Instead, we’ll aim to find an alternative to the upper bound, some value $r_k \in \textbf{R}$ that we can prove is larger than a significant portion of $\textbf{R}$.

We’ll begin with a brief look at arbitrary graphs. Any results from this general case should also apply to our analysis on complete graphs.

$\textbf{Definition}:$ The $\textit{diameter}$ of a graph is the maximum shortest path distance between any pair of nodes. For a graph $\Big(\textbf{G)}$ with a set of vertexes $\Big(\textbf{V})$:

$$\begin{equation} \text{Diam}\Big(\textbf{G}) = \max\{ \ d\Big(v_i,v_j) \ | \ v_i, v_j \in \textbf{V} \ \} \end{equation}$$

Where $d \colon V \times V \to \mathbb{R}$ a distance function defined on the graph. We’ll assume graphs are $\textit{unweighted}$ and $d\Big(v_i, v_j)$ is simply the count of edges between $v_i$ and $v_j$.

On an $\textbf{arbitrary graph}$ with an update initialized at $v_o$ we can see that $R_g \geq \max\{\ d\Big(v_o,v_j) \ | \ v_j \in \textbf{V} \ \}$. In the worst case, $v_o$ is in the pair of nodes that define the diameter. In that event, we have $R_g \geq \text{Diam}\Big(\textbf{G})$.

This inequality simply asserts that an update cannot travel further from its origin node than rounds have elapsed. If $v_o$ is five nodes from its furthest peer, we can be certain the algorithm does not complete in four rounds. This is a fine observation, but we can construct examples where $\text{Diam}\Big(\textbf{G})$ is well below the minimum of $R_g$. One such example is a $\textbf{wheel graph}$.

From looking at an $n$ node wheel graph, we can see $R_g \geq n - 1$ regardless of the location of $v_o$. There are just two cases to consider:

• The central node is the origin node. This node must send at least $n - 1$ messages to update the $n - 1$ outer nodes.

• An outer node is the origin node. This node sends one message to the central node, and the central node sends at least $n - 2$ messages to update the remaining nodes.

$\textbf{Comment}$: A wheel graph is among the worst possible configurations for gossip. Do you see why this is the case?

Assume an $n$ node wheel graph with the central node as the update origin. With $j \in \Big[1, n)$ nodes updated, the probability the central node gossips to a non-updated node is $(n - j)/n$. If you’ve taken a course on probability, you may recognize this as the coupon collector’s problem. The expected number of rounds to complete the gossip process is $\textit{exactly the same}$ as the solution to this well-studied problem:

$$E\Big(R_g) = nH_n = n\sum_{k=1}^{n}\frac{1}{k} \approx n \text{ln}\Big(n) + 0.5772 + 1/2n$$

The expectation of $R_g$ doesn’t give any insight into the worst-case performance of the algorithm. We can approximate the right tail of the distribution by studying a single node’s state after $t$ rounds.

$$\begin{equation} \begin{align} \textit{Pr}(\textit{not updated}) & = & (1 - 1/n)^t \\ & \leq & e^{-t/n} \quad & \textit{Use Fact: } \big(1 - 1/n)^k \leq e^{-k/n} \\ & = & e^{-(n\text{ln}\Big(n) + cn)/n} \ \qquad & \text{Set: } t = n\text{ln}\Big(n) + cn \\ & = & 1/ne^{c} \end{align} \end{equation}$$

Finally, we union bound over $n$ nodes and find the probability that $R_g \geq n\text{ln}\Big(n) + cn$ is $n/ne^{-c} = e^{-c}$. For large $n$, this bound nicely relates the completion probability and the number of rounds beyond the expectation.

Using specific information about a graph allows us to produce a tighter bound than we could otherwise. In the next section we’ll apply this thinking to produce a lower bound on complete graphs.

Let’s turn our focus to $\textit{complete graphs}$. As with wheel graphs, the diameter is not a tight lower bound for $R_g$. Let’s try running a simulation and seeing if it reveals any interesting patterns.

At right, I show the results from 10,000 iterations of the gossip process in a 64 node system. The first plot shows the updated nodes over time, the second shows the distribution of completion times, and the third shows the round-over-round growth rate.

If we had a reliable way to describe this probability distribution as a function of $n$ our job would be done. Unfortunately, we’re not there yet.

Let’s define $U_t$ as the number of updated nodes after $t$ rounds. Notice that near the beginning of the process $U_t$ nearly doubles in each round. Because we send just one message per node-round, doubling $U_t$ is the optimal outcome for any round. As $U_t$ increases, message efficiency decreases and we expect less round-over-round growth.

Though incredibly unlikely, we $\textit{could}$ double $U_t$ in each round through the entire gossip process. If this were to happen, the process would complete in $\lceil \log_2\Big(n) \rceil$ rounds. This gives us our greatest lower bound on $R_g$, gossip will never complete before $\lceil \log_2\Big(n) \rceil$ rounds! The graph at right simulates a system with eight nodes completing gossip in $\lceil \log_2\Big(8) \rceil = 3$ rounds.

$\textbf{Comment:}$ Consider that it requires at least $n - 1$ messages to update $n - 1$ nodes. The function $M\Big(j, n)$ calculates the maximum messages sent through $j$ rounds in an $n$ node system, $j = \lceil \log_2\Big(n) \rceil$ is the smallest value that satisfies $M\Big(j, n) \geq n - 1$ for $n \geq 2$.

$$\begin{equation} M\Big(j, n) = \sum_{k = 0}^{j-1} \min\Big(2^k, n) \end{equation}$$

With a randomized algorithm the probability that gossip completes in $\lceil \log_2\Big(n) \rceil$ rounds is $\textit{very small}$ when $n$ is large. For example, A $2^k$ node system can complete in $k$ steps if $2^{k - 1}$ nodes are already updated through $k - 1$ rounds and the $k^{th}$ round is executed perfectly. Conditioning on the former, the probability of the latter event is $\prod_{x=1}^{2^{k-1}} x / 2^k$. Even at small values of $k$ this event is very improbable (e.g. $k=3$ gives $\approx 0.58\%$ success probability).

We could design a $\textit{deterministic}$ algorithm that always finishes in $\lceil \log_2\Big(n) \rceil$ rounds (ignoring unreliable networks, failed nodes, etc.). This choice is probably not ideal in most distributed systems as it trades fault tolerance for a relatively minor performance improvement.

Earlier I claimed we’d aim to find an upper bound on $R_g$. This was misleading, no such bound exists. For systems with $n > 2$, we can show that $R_g$ is unbounded from above.

Consider a three node system with two updated nodes. For gossip to complete in the next round, either of the updated nodes must message the third. Because this is a randomized algorithm there is a small probability the first two nodes gossip between themselves indefinitely.

$\textbf{Definition}:$ The probability mass function (pmf) of the geometric distribution is given by:

$$\begin{equation} f\Big(X=r) = (1-p)^{r-1} \cdot p \ , \ r \in \mathbb{N} \end{equation}$$

The probability a round passes without a message sent to the third node is $\Big(1/2)^2 = 1/4$. Because peers are chosen independently, the distribution of the number of rounds until the third node is updated is geometric with parameter $p = 3/4$. Although the pmf of $\text{Geom}\Big(3/4)$ decreases quite quickly, the distribution is memoryless and assigns non-zero probability to all $r \in \mathbb{N}$.

Do we stop our analysis here and say we’re limited to “On an undirected complete graph $\textit{Pr}\Big(R_g = r) > 0$ for all $r \in [\log_2\Big(n), \infty)$”?

No, surely we can do better. In the following sections we’ll provide an alternative to the upper bound by estimating how often $R_g$ exceeds any given value.

So far, we’ve found a lower bound and shown the non-existence of an upper bound. Before finding an alternative to the upper bound we’ll find the expectation of $R_g$. In some literature, gossip algorithms are referred to as “epidemic algorithms” and analyzed using models from epidemiology. We’ll use a similar model to find the expected number of updated nodes as a function of rounds, $u\Big(t)$.

Let’s model $du/dt$ as a function of updated nodes, non-updated nodes, and the “contact rate” between any pair of an updated and non-updated node. On a complete graph there are $\big(n - u)u$ edges between these pairs. Instead of a “contact” rate, we’ll treat $\big(\beta)$ as the update probability per edge-round.

$$\begin{equation} \frac{du}{dt} = \beta\Big(n - u)u \end{equation}$$

To match the literature, we’ll use $\beta=1/n$ as the contact rate, but we should have some reservations about this choice. Think about this choice, does it imply a faster or slower gossip process than what we described previously?

A constant $\beta$ implies any updated node will update any non-updated node with fixed probability (e.g. $1/n$). This is an $\textit{overestimate}$ of the contact rate and implies a faster completion time. This value ignores collisions and the one message per node-round cap we’ve imposed. It’s an OK approximation for the moment but better estimates are available.

$$\begin{equation} \frac{du}{dt} = \beta\Big(n - u)u \ \ ,\ \ \ u\big(0) = 1 \end{equation}$$

If we solve for $u\big(t)$ and set $t = k\text{ln}\Big(n)$, we get an equation that allows us to draw a some nice conclusions about the average performance of the algorithm.

$$\begin{equation} \begin{aligned} u\big(t) & = & \frac{ne^{\beta n t}}{e^{\beta nt} + n - 1} \\ & = & \frac{ne^{t}}{e^{t} + n - 1} \\ & = & \frac{n^{k + 1}}{n^k + n - 1} \qquad \textit{Set: } t=2\text{ln}\big(n) \end{aligned} \end{equation}$$

When $n$ is large and $t = 2\text{ln}\big(n)$, $u\big(t) \approx n - 1$. With this, we can say that after $2\text{ln}\big(n)$ rounds almost all nodes have received the update, $E\big(R_g) \approx 2\text{ln}\big(n)$.

$\textbf{Comment:}$ For a moment, we’ll ignore the fact that $2\text{ln}\big(n)$ is an underestimate of $E\big(R_g)$ for any given $n$. We can estimate the total messages sent by integrating $u\big(t)$.

$$\begin{equation} \begin{aligned} \int \frac{ne^{t}}{e^{t}+n-1} \ dt & = & n\text{ln}\big(e^t + n - 1) \\ & \approx & nk\text{ln}\big(n) - n\text{ln}\big(n) \\ & = & n\big(k - 1)\text{ln}\big(n) \ \ , \ \ k > 1 \end{aligned} \end{equation}$$

For a 128 node system this gives us an expectation of $622$ messages. Does this seem lightweight to you?

The choice of $\beta$ is quite important. We can set $\beta$ to be dependent on the current state of the system. By considering message collisions we’ll produce a more conservative estimate. From the perspective of a single, non-updated node the probability of being updated by $\textit{any}$ one of $u$ updated nodes is:

$$\begin{equation} \beta = \big(1 - \big(1 - 1/n)^u)u^{-1} \approx \big(1 - e^{-u/n})u^{-1}. \end{equation}$$

Where $\big(1 - \big(1 - 1/n)^u)$ represents the probability of being updated by at least one node. We divide that value by $u$ to give the average update rate per edge. Using this value as $\beta$ gives:

$$\begin{equation} \begin{aligned} \frac{du}{dt} & = & \big(1 - e^{-u/n})\Big(n - u) \\ & \approx & \ \big( u/n - u^2/2n^2 )\big(n - u) \qquad \text{By Taylor Expansion} \\ \end{aligned} \end{equation}$$

We can solve this equation as well, but the solution is not quite as nice. If we set $u\big(t) = n - 1$ how much longer to we expect the gossip process to take? Our prior analysis gives $\sim 8.32$ rounds but the more precise analysis gives $\sim 11.78$ rounds. From the simulations run in $\textbf{section 2}$, 11.8 seems like a much more reasonable estimate than 8.32. How did this happen?

As it turns out, we have not stumbled into a decades-long error in the theoretical computer science community. These numbers are quite different, but we can show these two functions behave well asymptotically. To do so, we’ll solve both equations as functions of $t$ and compare the ratios as $n \to \infty$.

Using the original model that ignores collisions and the a message cap we get $t \approx 2\text{ln}\big(n)$ as expected.

$$\begin{equation} n - 1 = \frac{ne^{t}}{{e^{t} + n - 1}} \implies t \approx \text{ln}\big(n^2) = 2\text{ln}\big(n) \end{equation}$$

To solve the equation with collisions and a message cap, we’ll treat $n$ and $n - 1$ as equivelent and solve the following equation:

$$\begin{equation} n - 1 = \frac{n \big(2 n e^t - n \big(-n + \sqrt{n^2 + 2 n e^t}))}{n^2 + 2 n e^t} \implies t \approx \text{ln}\big(n^3/2) \end{equation}$$

When $n$ is large, the ratio of these two functions is 1.5. The key result from this diversion is that a result obtained using $\beta = 1/n$ is of the same order (technically $\Theta\big(ln\big(n))$, see: Landau notation) as the result obtained from a more rigorous analysis. Let’s revise our statement from earlier, $E\big(R_g) \approx 3\text{ln}\big(n/2)$.

We’re still in search of a way to describe the right tail of the distribution of $R_g$. In this section we’ll calculate the distributions of the $\textit{time}$ the system spends with exactly $u$ nodes updated. This approach will confirm our previous result about the expected completion time and provide the variance for the entire process.

As in the previous section, we’ll assume each of $\big(n - u)u$ edges sends a message with probability $\beta = 1/n$ per round. Because peer selection is randomized, we may treat the time to send a message on any edge as exponentially distributed with mean of $n$ rounds (i.e. $\textit{Exp}\big(1/n)$).

Regardless of the number of rounds elapsed, the waiting time until $u$ is incremented is distributed as the minimum of $\big(n - u)u$ independent exponential variables with parameter $n$.

Using order statistics we can show that the $\textit{minimum}$ value from a sample of $k$ exponential random variables with parameter $\lambda$ is exponentially distributed with parameter $k\lambda$. In our case, the time until another node is updated is distributed as $\textit{Exp}\big(\frac{u\big(n - u)}{n})$.

$\textbf{Definition:}$ The probability distribution function (pdf) and cumulative distribution function (cdf) of the exponential distribution are given by:

$$\begin{equation} \begin{align} f\big(X = r) & = & \lambda e^{-\lambda x} & \qquad \textit{probability distribtion} \\ F\big(X = r) & = & 1 - e^{-\lambda x} & \qquad \textit{cumulative distribution} \end{align} \end{equation}$$

An exponential distribution with parameter $\lambda$ has mean $1/\lambda$ and variance $1/\lambda^2$.

$\textbf{Definition:}$ The $k^{th}$ order statistic is the $k^{th}$ smallest value from a sample of $n$ random variables. If we know the distribution used to generate a sample, we can determine the distribution of any order statistic of that sample. Generally, the $k^{th}$ order statistic is given as:

$$\begin{equation} F_X_\left(k\right) \big(x) = \sum_{j=k}^{n} \binom{n}{j} [F_x\big(x)]^j [1 - F_x\big(x)]^{n-j} \end{equation}$$

In each term we calculate the probability that $j$ events are smaller and $n-j$ events are larger than $x$. When $k = 1$ we have a special case that allows us to simplify this sum to:

$$\begin{equation} F_X_\left(k\right) \big(x) = 1 - [1 - F_x\big(x)]^{n} \end{equation}$$

And when the sample is exponential, we get:

$$\begin{equation} \begin{aligned} F_X_\left(k\right) \big(x) & = & 1 - [1 - \big(1 - e^{-\lambda x})]^{n} \\ & = & 1 - e^{-n\lambda x} \end{aligned} \end{equation}$$

This result gives us the cumulative distribution of $\textit{Exp}\big(n\lambda)$.

We’ve completed the challenging work of formulating the problem, now we must compute the expectation and variance on each interval. Let’s define $\tau_u$ as the first time the system has at least $u$ nodes updated. We’ll then confirm that $E\big(\tau_n) \approx E\big(R_g)$. Our new framing of the problem should preserve our expectation of $R_g$.

$$\begin{equation} \begin{aligned} E\big(\tau_n) & = & \sum_{u = 1}^{n - 1} \frac{n}{u\big(n - u)} \\ & = & \sum_{u = 1}^{n - 1} \frac{1}{u} + \frac{1}{\big(n - u)} \quad \textit{as partial fractions}\\ & \approx & 2 H_{n} \\ & \approx & 2 \text{ln}\big(n) + 0.5772 + \frac{1}{2n} \quad \textit{approx. of Harmonic Series} \\ & \approx & 2\text{ln}\big(n) \end{aligned} \end{equation}$$

Excellent, just as expected! Because the waiting times are independent variables we can sum the variances of all waits to get $\textit{Var}\big(\tau_{n})$.

$$\begin{equation} \begin{aligned} \text{Var}\big(\tau_n) & = & \sum_{u = 1}^{n - 1} (\frac{n}{u\big(n - u)})^{2} \\ & = & \sum_{u=1}^{n-1} \frac{1}{u^{2}} + \frac{1}{\big(n-u)^{2}} - \frac{2}{n^2 - nu} \quad \textit{as partial fractions} \\ & \approx & \sum_{u=1}^{n-1} \frac{1}{u^{2}} + \frac{1}{\big(n-u)^{2}} \\ & \approx & 2 \pi^2 / 6 \\ \end{aligned} \end{equation}$$

The last approximation uses the fact that the sum of inverse squares (see: The Basel Problem) converges to $\pi^2/6$. When $n$ is sufficiently large we can approximate $\sum_{i=1}^{n - 1}\left(1/u^2 + 1/\big(n - u)^2 \right)$ as $\pi^2/6$. This is a very interesting sum by itself, but it also gives us a very useful result. It suggests variance is bounded!

$\textbf{Comment}$: The variance of $\tau_n$ is almost entirely comprised of the variance waiting on the first and last few nodes. Consider an $n$ node system with one updated node. In the discrete case, we’d expect the waiting time to update a second node to be tightly concentrated around one round.

However, the distribution for the first wait is $\textit{Exp}\big(\frac{n-1}{n})$. This distribution provides a mean that matches our intuition, but also produces $\textit{Var}\big(\tau_2) = 1$. Does this seem reasonable? Counter-intuitively, adding the first additional node is responsible for almost a third of the reported variance.

In the last section we showed $3\text{ln}\big(n/2)$ is a more reasonable estimate for $E\big(R_g)$ than $2\text{ln}\big(n)$. Can we show the variance is still bounded when $du/dt = \big(1 - e^{-u/n})\big(n - u)$?

$$\begin{equation} \begin{aligned} \left(\big(n - u)\big(\frac{u}{n} - \frac{u^2}{2n^2})\right)^{-1} & = & \frac{1}{u - 2n} - \frac{2}{u - n} + \frac{1}{u} \\ \left(\big(n - u)\big(\frac{u}{n} - \frac{u^2}{2n^2})\right)^{-2} & = &\frac{1}{\big(u - 2n)^2} + \frac{4}{\big(u - n)^2} + \frac{3}{nu} + \frac{1}{u^2} - \frac{3}{n\big(u - 2n)} \\ \end{aligned} \end{equation}$$

$$\begin{equation} \begin{aligned} \text{Var}\big(\tau_n) & = & \sum_{u=1}^{n-1} \frac{1}{\big(u - 2n)^2} + \frac{4}{\big(u - n)^2} + \frac{3}{nu} + \frac{1}{u^2} - \frac{3}{n\big(u - 2n)} & \approx & 5 \pi^2 / 6 \end{aligned} \end{equation}$$

We can! So what are the implications of having bounded variance? We confirmed that $E\big(\tau_n)$ increases slowly with $n$ and showed $\tau_n$ stays near the expectation even for very large $n$. If we use gossip to disseminate information in massive systems we don’t need to worry about worst case performance becoming orders of magnitude worse than the expectation.

We should be a but careful about this estimate though. We can show that the second-degree Taylor series $\textit{overestimates}$ the variance when $u$ is near $n$. It’s possible this would improve with a better approximation, but we’ll proceed for now.

We’re still missing a tidy answer to the question posed in the first section. If we had the distribution of $\tau_n$ we could find the cumulative distribution function and we’d have a neat final answer. Unfortunately, we’ll have to rely on one more approximation before moving on.

$\textbf{Comment:}$ Having a probability distribution for gossip time would be a very satisyfing result. The sum of $k$ exponentials with the same parameter is called the Erlang distribution, it’s a specific case of the gamma distribution. Is there an argument we can make that allows us to just use the gamma?

Chebyshev’s Inequality bounds the probability a random variable deviates from its mean by more than a given amount. It’s an incredibly general result and requires only the variance of the distribution.

$$\begin{equation} P(|X - \mu| \geq c) \leq \frac{\text{Var}(X)}{c^2} \end{equation}$$

By definition, Chebyshev’s ineuquality provides another $\textit{overestimate}$ of the probability that gossip exceeds x rounds to finish. Consequently, given an n node system, the probability that gossip fails to complete within x rounds is no more than:

$$\begin{equation} p \leq \frac{5\pi^2}{6\big(x - 3\ln\big(n))^2} \end{equation}$$

For today, this is a satisfactory answer. I’d encourage you to try a few values. What is an upper bound on the 99th percentile of gossip time on a 1M node distributed system?

$\textbf{Comment:}$ This is an OK answer. We set out to understand the risk of large divergences when $n$ is very large, but what if we $\textit{really}$ needed a distribution? I suggest two options:

• The maximum-entropy distribution given a minimum ($\log_2\big(n)$) and a mean ($3\ln\big(n)$) follows the pareto distribution. Can you solve for the shape parameter of the Pareto to find a closed form distribution which we $\textit{know}$ will overstimate the weight on the tails?

• If we want a more realistic (rather than more conservative estimate) we might use method of moments to fit the mean and variance of this distribution to an Erlang distribution. The erlang distribution is given by the sum of $k$ exponentials with fixed parameter ($\lambda$). Although we have mixed parameters, can some approximation using some $k$ and $\lambda$ get close?

$\textbf{Second Degree Taylor Series Overestimates Variance}$

Finally, I’d like to mention a few variations of the idealized gossip algorithm that can make it more suitable for real-world distributed systems. This section does not build on any previous results, but instead answers a few questions about making gossip more robust.

We haven’t described a mechanism for $\textbf{stopping}$ gossip. In distributed systems we communicate information about remote state by passing messages, so are we meant to send another round of messages to signal that gossip has completed?

Not necessarily! From the previous section, we expect that gossip completes in $\sim3\text{ln}\big(n/2)$ rounds. If we set $3k\log\Big(n)$ as a cap on the number of rounds gossiped per node, for some $k > 1$, all nodes will be updated $\textit{before}$ the algorithm stops. We can set $k$ even higher to achieve a given success probability. However, there are less message intensive solutions. Demers demonstrates we can achieve the same completeness guarantees if we deactivate nodes with probability $1/n$ after each message they send to an already updated node.

The graph at right illustrates what happens when the deactivation probability is set $\textit{too high}$. When set properly the failure percentage is near zero. In this example, the algorithm will fail in ~20% of attempts.

In $\textbf{Section 3}$ we assumed $\beta = 1/n$ and then in $\textbf{Section 4}$ revised these values to be a bit more realistic. What about redoing those calculations with $\beta = k/n, k > 1$? This suggests faster gossip time at the cost of some additional message overhead. Can we simply select multiple peers per round? What about broadcasting a single update to $\textit{all}$ nodes in the network in a single round?

Gossiping multiple point-to-point messages per round can be an effective way to improve the speed of the gossip algorithm. However, broadcasting an update to all nodes from a single site (“single-round broadcast”) is normally not the best choice in large distributed systems.

We’ve mostly focused on idealized models of distributed systems, but in practice we must account for unreliable networks and incomplete information. Creating a reliable broadcast from point-to-point messages helps us be resilient to both of these failure modes. We $\textit{can}$ construct reliable broadcast from single-round broadcast, but it comes at a cost of significantly more messages transmitted when networks are unreliable.

The graphs above illustrate how reliable broadcast built from point-to-point messaging and single-round broadcast perform when faced with unreliable networks.

Highly correlated traffic is a common occurrence in real systems. Imagine a system that receives twenty updates in quick succession. Should we initialize twenty unique gossip processes or is there a more efficient way to spread this information?

One solution is to use pull-based messaging. With pull-based difference resolution, every node contacts one peer per round and we mark a node updated if they’ve $\textit{contacted}$ an updated node. When there are many active updates, Its likely to a node contacts a peer with at least one new update.

However, if the system receives updates infrequently and far apart, pulling creates additional messaging overhead with relatively little benefit.

The average performance of pull-based messaging is a bit faster than the standard (push) algorithm. We can approximate the probability a node has not been updated after $i$ rounds as a recurrence relationship for both push and pull-based gossip.

$$\begin{equation} \begin{align} p_{i + 1} & = & p_i\Big(1 - 1/n)^{n\Big(1-p_i)} \\ p_{i + 1} & = & p_i^2 \\ \end{align} \end{equation}$$

In the earlier rounds, the performance of the two algorithms is close because $p_i \approx \big(1 - 1/n)^{n\big(1 - p_i)}$. When $p$ is smaller, the pull-based algorithm decreases to zero quadratically while the push based method decreases by a constant factor $\frac{1}{e}$.

It was demonstrated that using a combination of push in the beginning and then pull towards the end, total messages sent and time to finish gossip can be improved compared to either algorithm in isolation.

This concludes our tour of gossip algorithms. Let’s do a brief review:

• Gossip is used to spread information in a distributed system and is resilient to incomplete membership information and unreliable networks.

• Gossiping with point-to-point messaging starts relatively slowly and has a minimum of $\lceil\text{log}_2\big(n)\rceil$ rounds.

• The number of rounds needed to complete the gossip process is unbounded from above.

• Gossip scales well as the number of nodes in a system increases, $E\big(R_g) \approx 3\text{ln}\big(n/2)$

• $\textit{Var}\Big(R_g)$ is bounded. We can show that the probability the gossip process exceeds $3\text{ln}\big(n/2) + c$ rounds is $\leq 5\pi^2/6c^2$.

• Variations can be made on the idealized gossip algorithm to make it more suitable for use in real distributed systems.

Thanks for reading! I’ve enjoyed studying gossip algorithms the past few weeks because they’re easy to understand and easy to implement, but analyzing them involves pulling together bits of mathematics from many areas of study. If you’re an engineer reading this, hopefully its gotten you to think of analysis of algorithms as a bit more than a set of facts about complexity. If you’re a math enthusiast, hopefully you’ve learned a bit more about distributed computer systems and are able to apply techniques mentioned in this post to your own problems.