papers/lp-205-pipelined-quasar/sections/03-depth-and-leader-rotation.tex

\section{Pipeline Depth and Leader Rotation}

Pipeline depth is the number of consecutive blocks in flight at any
instant. Depth~$3$ is the reference.

\begin{table}[h]
\centering
\small
\begin{tabular}{@{}rp{5cm}p{6cm}@{}}
\toprule
\textbf{$D$} & \textbf{Stage occupancy} & \textbf{Bound} \\
\midrule
$1$ & Sign($N$) only & Round-blocking baseline; tput $= 1 / \mathrm{cert\_wall}$ \\
$2$ & Sign($N$), Build($N{+}1$) & tput $= 1 / \max(\mathrm{build}, \mathrm{cert\_wall})$ \\
$3$ & Sign($N$), Build($N{+}1$), Select($N{+}2$) & tput $= 1 / \max(\mathrm{select}, \mathrm{build}, \mathrm{cert\_wall})$ \\
$\geq 4$ & extra Select stages & Bounded by leader-rotation independence; gain saturates \\
\bottomrule
\end{tabular}
\caption{Pipeline depth and the corresponding bound on
single-leader throughput.}
\label{tab:depth}
\end{table}

\paragraph{Depth-3 saturation.} Depth~$3$ saturates the per-block
stage list. A fourth in-flight block either repeats a stage (two
Select stages on different blocks) or operates ahead of leader
rotation. The first case is bounded by stage independence; the
second is bounded by the leader-rotation contract.

\subsection{Depth bound}

The hard depth bound is:

\begin{equation}
D_{\max} = \min\bigl(
  c_{\textrm{round-independence}}, \;
  c_{\textrm{leader-rotation}}, \;
  c_{\textrm{mempool-speculation}}
\bigr)
\end{equation}

\noindent where each $c_{\cdot}$ is the corresponding subsystem's
independence ceiling.

For Lux validator sets with round-robin leader rotation, each
$c_{\cdot}$ is at least $N$ (validator count). For VRF-weighted
random rotation, the minimum is $\min(N, c_{\textrm{distinct-leaders}})$
where $c_{\textrm{distinct-leaders}}$ is the expected consecutive
distinct-leader count. Depth~$3$ is safe against both rotation
schemes for any $N \geq 4$.

\subsection{Leader rotation}

Pipelined Quasar requires that every in-flight block has a
different leader. Otherwise a single byzantine leader can stall the
pipeline by withholding its block at multiple in-flight heights.

\paragraph{Round-robin rotation.} Leader at height $H$ is
\texttt{validators[H mod N]}. Pipeline depth~$3$ requires
\texttt{validators[H]}, \texttt{validators[H+1]},
\texttt{validators[H+2]} are distinct, which holds for any $N \geq 3$.

\paragraph{VRF-weighted random rotation.} Leader at height $H$ is
sampled from the stake-weighted validator set via VRF over the
previous block's randomness beacon. Pipeline depth~$3$ requires
three consecutive distinct samples; on stake-weighted draws this
holds with probability
$1 - (s_{\textrm{top}}/s_{\textrm{total}})^2$ per step. For a sane
stake distribution ($s_{\textrm{top}} \leq s_{\textrm{total}}/3$),
this is $> 89\%$ per height.

\paragraph{Non-distinct leader at depth.} When the rotation produces
a non-distinct leader, the pipeline shortens: the second instance of
that leader's block waits for its predecessor to complete Sign
before entering its own Build stage. Shortened-depth pipelining is
throughput-degraded but liveness-preserving.