papers/hanzo-dso/sections/14-gossip-protocol-formal-analysis.tex

\section{Gossip Protocol Formal Analysis}

\label{app:gossip}

\begin{theorem}[Gossip Convergence]
In a connected graph with $n$ nodes and minimum degree $d_{\min} \geq 3$, the
pull-based gossip protocol (Algorithm~\ref{alg:gossip}) ensures that a new
prior reaches all honest nodes within:
\begin{equation}
    T \leq \left\lceil \frac{3 \ln n}{\ln d_{\min}} \right\rceil \cdot \Delta t_{\text{gossip}}
\end{equation}
rounds with probability $\geq 1 - 1/n$.
\end{theorem}

\begin{proof}
At each round, an uninformed node contacts $d_{\min}$ random peers. The
probability that at least one peer is informed is $1 - (1 - p_t)^{d_{\min}}$
where $p_t$ is the fraction of informed nodes at time $t$. Using the standard
rumor spreading analysis~\cite{demers1987epidemic}, the fraction of informed
nodes satisfies:
\begin{equation}
    p_{t+1} \geq 1 - (1 - p_t) \cdot (1 - p_t)^{d_{\min}} = 1 - (1 - p_t)^{d_{\min}+1}.
\end{equation}
Starting from $p_0 = 1/n$, after $O(\log n / \log d_{\min})$ rounds, $p_t > 1 - 1/n$.
\end{proof}