papers/lux-photon-protocol/sections/05-pipeline-stall-analysis.tex

\section{Pipeline Stall Analysis}

\label{sec:stalls}

\subsection{Stall Definition}

\begin{definition}[Pipeline Stall]
A stall occurs when a pipeline slot $s$ fails to increment its leading confidence
counter for $\tau$ consecutive rounds, blocking the slot from finalization and preventing
new transactions from entering.
\end{definition}

\begin{theorem}[Stall Duration]
\label{thm:stall}
The expected stall duration (number of consecutive non-incrementing rounds) for a
pipeline slot is:
\[
\mathbb{E}[\tau] = \frac{1}{q_1} + O\left(\frac{q_0}{q_1^2}\right)
\]
which is $O(1)$ when $q_1 > 1/2$.
\end{theorem}

\begin{proof}
A non-incrementing round occurs when the sample does not produce a supermajority for
the leading color. After population convergence (which takes $O(\log n)$ rounds), the
probability of a supermajority round is $q_1 \approx \Phi(p, k, \alpha)$ where $p > 1 - \gamma$.

The number of rounds until the next supermajority round follows a geometric distribution
with parameter $q_1$, giving $\mathbb{E}[\tau] = 1/q_1$. For $q_1 = 0.63$ (standard
parameters with $p = 0.8$, $k = 20$, $\alpha = 0.8$), the expected stall is $1.6$ rounds.
\end{proof}

\begin{corollary}[Pipeline Utilization]
\label{cor:utilization}
The expected pipeline utilization (fraction of rounds where at least one slot advances)
is $1 - (1 - q_1)^m$, which exceeds 0.99 for $m \geq 7$ with standard parameters.
\end{corollary}

\begin{proof}
A round is wasted only if none of the $m$ active slots produce a supermajority. Since
the slots' supermajority events are independent (for independent conflict sets), the
probability of a fully idle round is $(1 - q_1)^m = (0.37)^m < 0.01$ for $m \geq 7$.
\end{proof}

%% -----------------------------------------------------------------------
%%  6. THROUGHPUT ANALYSIS
%% -----------------------------------------------------------------------