papers/lux-nova-protocol/sections/04-throughput-analysis.tex

\section{Throughput Analysis}

\label{sec:throughput}

\subsection{Burst Size Distribution}

\begin{theorem}[Expected Burst Size]
\label{thm:burst-size}
If transactions arrive at rate $T$ (transactions per round) and frontier vertices
finalize at rate $\lambda$ (vertices per round), the expected burst size is:
\[
\mathbb{E}[|\text{burst}|] = \frac{T}{\lambda} \cdot \left(1 + \frac{T}{n \cdot \text{fan-in}}\right)
\]
where $\text{fan-in}$ is the average number of parents per vertex.
\end{theorem}

\begin{proof}
Between consecutive frontier finalization events (which occur at rate $\lambda$), an
expected $T/\lambda$ new transactions arrive and are appended to the DAG. Each new
transaction references existing frontier vertices as parents, with an average fan-in.

When a frontier vertex $v$ finalizes after accumulating $\beta$ rounds of confidence,
its cone includes all transactions that were added since the last finalization of $v$'s
predecessors. In steady state, each cone contains $T/\lambda$ vertices on average.

The correction factor $1 + T/(n \cdot \text{fan-in})$ accounts for overlapping cones
when multiple frontier vertices share common ancestors. With high fan-in (each new
vertex references many parents), cones overlap more, slightly increasing burst size.
For typical parameters ($T = 1000$, $n = 1000$, fan-in $= 4$), the correction is
$1 + 1000/4000 = 1.25$.
\end{proof}

\subsection{Effective Throughput}

\begin{corollary}[Nova Throughput]
\label{cor:throughput}
The effective throughput of Nova (finalized transactions per second) equals the
transaction arrival rate $T$, independent of the consensus finalization rate $\lambda$,
as long as $\lambda > 0$ (the protocol eventually finalizes frontier vertices).
\end{corollary}

\begin{proof}
In steady state, every arriving transaction is eventually included in some vertex's
cone and finalized in a burst. The burst mechanism ensures that even if individual
vertex finalization is slow ($\lambda$ is small), larger bursts compensate by
finalizing more transactions per event. The throughput is:
\[
\text{Throughput} = \lambda \cdot \mathbb{E}[|\text{burst}|] = \lambda \cdot \frac{T}{\lambda} = T
\]
\end{proof}

\subsection{Amortized Communication}

\begin{lemma}[Communication Complexity]
\label{lem:communication}
The amortized message complexity per finalized transaction is $O(k / \mathbb{E}[|\text{burst}|])$,
which is $O(k\lambda/T)$ messages per transaction.
\end{lemma}

\begin{proof}
Each round of frontier sampling requires $k$ query messages per frontier vertex.
Each frontier vertex requires $\beta$ rounds of sampling before finalization,
consuming $\beta \cdot k$ messages. The burst triggered by that vertex finalizes
$\mathbb{E}[|\text{burst}|] = T/\lambda$ transactions. The amortized cost per
transaction is $\beta k / (T/\lambda) = \beta k \lambda / T$.

For $\beta = 11$, $k = 20$, $\lambda = 5$ (5 frontier vertices finalize per round),
and $T = 1000$ transactions per round: the amortized cost is
$11 \cdot 20 \cdot 5 / 1000 = 1.1$ messages per transaction, vastly better than
the $O(n)$ per-transaction cost of leader-based protocols.
\end{proof}

%% -----------------------------------------------------------------------
%%  5. SAFETY AND LIVENESS
%% -----------------------------------------------------------------------