papers/lux-nebula-protocol/sections/04-convergence-analysis.tex

\section{Convergence Analysis}

\label{sec:convergence}

\subsection{Mixing Time in Sparse Graphs}

\begin{theorem}[Nebula Convergence]
\label{thm:nebula-convergence}
In a random geometric graph $G(n, r)$ with expansion factor $\xi$, the Nebula protocol
converges in $O(\log n / \xi)$ rounds with probability $1 - e^{-\Omega(k)}$.
\end{theorem}

\begin{proof}
The convergence of the metastable dynamics depends on how quickly information propagates
across the network. In a well-connected graph, a preference bias amplifies globally in
$O(\log n)$ rounds because each sample reflects the global population fraction.

In a sparse graph, each sample reflects only the local neighborhood. The preference
bias propagates across the network through bridge validators at a rate proportional
to the expansion factor $\xi$.

Formally, define $p_i(r)$ as the fraction of validators in neighborhood $\mathcal{N}(v_i)$
preferring color 1 at round $r$. The local dynamics follow:
\[
p_i(r+1) = (1 - \xi) \cdot \Phi(p_i(r), k_L, \alpha) + \xi \cdot \Phi(\bar{p}(r), k_b, \alpha)
\]
where $k_L = k - k_b$ is the local sample size, $\bar{p}(r) = \frac{1}{n}\sum_j p_j(r)$
is the global average, and $\xi$ represents the fraction of bridge information.

The global average evolves as:
\[
\bar{p}(r+1) = \frac{1}{n} \sum_i p_i(r+1) \geq \Phi(\bar{p}(r) - \sigma/\sqrt{n}, k, \alpha)
\]
where $\sigma$ bounds the local variance.

By the standard amplification argument, $\bar{p}$ converges to 1 (or 0) in $O(\log n)$
rounds. The local fractions $p_i$ track $\bar{p}$ with delay $O(1/\xi)$, as information
must traverse $O(1/\xi)$ bridge hops to equilibrate. Total convergence time:
$O(\log n + \log n / \xi) = O(\log n / \xi)$ since $\xi \leq 1$.
\end{proof}

\subsection{Connectivity Threshold}

\begin{lemma}[Minimum Connectivity]
\label{lem:connectivity}
Nebula achieves consensus if and only if the network graph is connected. The minimum
communication radius for consensus is $r^* = c\sqrt{\log n / n}$ for the random
geometric graph model.
\end{lemma}

\begin{proof}
\textbf{Necessity}: If the graph is disconnected, two components can independently
converge to different preferences, violating safety.

\textbf{Sufficiency}: If the graph is connected, bridge validators ensure information
flow between all neighborhoods. The expansion factor satisfies $\xi > 0$ for connected
graphs, guaranteeing convergence by Theorem~\ref{thm:nebula-convergence} (possibly with
large delay for poorly connected graphs).

For $G(n, r)$, connectivity occurs with high probability when $r \geq c\sqrt{\log n / n}$
(Penrose's theorem). At this threshold, $\xi = \Theta(\log n / n)$, giving convergence
time $O(n / \log n \cdot \log n) = O(n)$---slow but convergent. For $r = c\sqrt{1/n}$
(expected degree $O(1)$), $\xi = \Theta(1/n)$ and convergence requires $O(n \log n)$ rounds.
\end{proof}

\subsection{Graceful Degradation}

\begin{corollary}[Graceful Degradation]
\label{cor:graceful}
As network connectivity degrades (smaller $r$, larger churn), Nebula's convergence
time increases smoothly as $O(\log n / \xi(r))$ without a sharp phase transition
at any particular connectivity level (other than complete disconnection).
\end{corollary}

%% -----------------------------------------------------------------------
%%  5. SAFETY AND LIVENESS
%% -----------------------------------------------------------------------