papers/lux-nebula-protocol/sections/06-partition-recovery.tex

\section{Partition Recovery}

\label{sec:partition}

\subsection{Partition Model}

We consider temporary network partitions where the network splits into components
$P_1, P_2, \ldots, P_m$ for a duration $T_p$, then reconnects.

\begin{proposition}[Partition Safety]
\label{prop:partition}
During a partition, Nebula halts finalization (does not finalize new transactions)
within each component that contains fewer than $2n/3$ validators. Components with
$\geq 2n/3$ validators continue to finalize safely.
\end{proposition}

\begin{proof}
Within a component $P_i$ with $|P_i| < 2n/3$, the sampling within $P_i$ cannot
guarantee honest supermajority (the $|P_i|$ validators include at most $|P_i| - f$
honest validators, which may be less than $\alpha k$ for small $|P_i|$). The Nebula
protocol detects insufficient responses and pauses finalization.

A component with $|P_i| \geq 2n/3$ contains $\geq 2n/3 - f > n/3$ honest validators,
sufficient for safety.
\end{proof}

\subsection{Post-Partition Reconciliation}

\begin{proposition}[Reconciliation Time]
\label{prop:reconciliation}
After partition healing, the Nebula protocol reconciles the network in $O(\log n / \xi + T_p \cdot \xi)$
rounds, where $T_p$ is the partition duration.
\end{proposition}

\begin{proof}
After reconnection, bridge validators propagate the latest state from the larger
partition to the smaller ones. The state divergence accumulated during $T_p$ rounds
creates a ``preference gap'' of at most $T_p$ confidence counts. This gap is resolved
by the standard convergence dynamics in $O(\log n / \xi)$ rounds, plus the time to
process the backlog of $T_p$ rounds of unfinalized transactions.
\end{proof}

%% -----------------------------------------------------------------------
%%  7. EVALUATION
%% -----------------------------------------------------------------------