papers/lux-nebula-protocol/sections/01-introduction.tex

\section{Introduction}

\label{sec:introduction}

Standard metastable consensus protocols assume a well-connected network where each
validator can reach any other validator with bounded delay. This assumption fails in
several important settings:

\begin{itemize}[nosep]
\item \textbf{Geographic distribution}: Validators in remote regions may have limited
connectivity to the broader network.
\item \textbf{Network partitions}: Temporary partitions create disconnected components
that must eventually reconcile.
\item \textbf{Bootstrap phase}: New blockchain networks start with few validators,
gradually growing the validator set.
\item \textbf{Appchains}: Lux appchains may have small validator sets (10--50 nodes)
with high churn rates.
\end{itemize}

Nebula adapts the metastable consensus framework to operate under these conditions by
replacing uniform random sampling with stratified neighborhood sampling, ensuring that
even in sparse networks, the consensus dynamics converge to agreement.

\paragraph{Contributions.}
\begin{enumerate}[nosep]
\item The Nebula stratified sampling protocol for sparse networks (\S\ref{sec:protocol}).
\item A random geometric graph model of sparse network consensus (\S\ref{sec:model}).
\item Convergence proofs under the expansion factor framework (\S\ref{sec:convergence}).
\item Safety and liveness analysis for sparse and partitioned networks (\S\ref{sec:safety}).
\item Empirical evaluation under packet loss and churn (\S\ref{sec:evaluation}).
\end{enumerate}

%% -----------------------------------------------------------------------
%%  2. SPARSE NETWORK MODEL
%% -----------------------------------------------------------------------