papers/lux-nebula-protocol/sections/02-sparse-network-model.tex

\section{Sparse Network Model}

\label{sec:model}

\begin{definition}[Random Geometric Graph]
The network is modeled as a random geometric graph $G(n, r)$: $n$ validators are
placed uniformly at random in $[0, 1]^2$, and validators $v_i, v_j$ can communicate
if $\|v_i - v_j\| \leq r$. The graph is connected with high probability when
$r \geq c\sqrt{\log n / n}$ for a constant $c > 0$.
\end{definition}

\begin{definition}[Neighborhood]
The neighborhood of validator $v_i$ is $\mathcal{N}(v_i) = \{v_j : \|v_i - v_j\| \leq r\}$.
The expected neighborhood size is $|\mathcal{N}(v_i)| \approx n \pi r^2$.
\end{definition}

\begin{definition}[Bridge Validator]
A validator $v$ is a bridge between neighborhoods $\mathcal{N}(v_i)$ and $\mathcal{N}(v_j)$
if $v \in \mathcal{N}(v_i) \cap \mathcal{N}(v_j)$. Bridges propagate consensus information
across the network.
\end{definition}

\begin{definition}[Expansion Factor]
The expansion factor $\xi$ of the network is:
\[
\xi = \min_{S \subseteq V, |S| \leq n/2} \frac{|\partial S|}{|S|}
\]
where $\partial S = \{v \notin S : \exists u \in S, v \in \mathcal{N}(u)\}$ is the
boundary of $S$. For random geometric graphs with $r = c\sqrt{\log n / n}$, $\xi = \Theta(1)$.
\end{definition}

%% -----------------------------------------------------------------------
%%  3. THE NEBULA PROTOCOL
%% -----------------------------------------------------------------------