Note on Gossiping on Star Graphs

A star graph is among the worst possible configurations for gossip. Assume an $n$ node star 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$.

$\textbf{Author's Note!}$ — This is a follow up to my 3B1B Summer of Math submission. You can read that in full here.

If you’ve taken a course on probability, you may have noticed a resembelence to the coupon collector’s problem. The expected number of rounds to complete the gossip process $\Big(R_g)$ 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 \Big(\log\Big(n) + 0.5772 + 1/2n)$$

The expectation of $R_g$ doesn’t give any insight into the worst-case performance of the algorithm. Instead, we can approximate the right tail of the distribution by studying a single peripheral 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\log\Big(n) + cn)/n} \ \qquad & \text{set: } t = n\log\Big(n) + cn \\ & = & 1/ne^{c} \end{align} \end{equation}$$

For a single node, the probability it has not been updated by the central node in $n\log\Big(n) + cn$ rounds is $1/ne^{c}$. Finally, we union bound over all $n-1$ peripheral nodes and find the probability that $R_g \geq n\log\Big(n) + cn \approx n/ne^{-c} = e^{-c}$.