papers/lux-quasar-benchmarks/sections/06-benchmark-4-message-complexity.tex

\section{Benchmark 4: Message Complexity}

\label{sec:messages}
%% ============================================================================

We measure actual network messages exchanged per committed block, not asymptotic
complexity class.

\begin{table}[h]
\centering
\begin{tabular}{@{}llrr@{}}
\toprule
\textbf{Protocol} & \textbf{Complexity Class} & \textbf{Msgs @ $n=21$} & \textbf{Msgs @ $n=100$} \\
\midrule
\textbf{Quasar}   & O($n$)   & 44        & 202 \\
HotStuff          & O($n$)   & 63        & 300 \\
Snow              & O($K \cdot \beta$) & 500 & 500 \\
Narwhal+Tusk      & O($n$)   & 84        & 400 \\
Tower BFT         & O($n$)   & 42        & 200 \\
Tendermint        & O($n^2$) & 441       & 10{,}000 \\
Casper FFG        & O($n$)   & 42        & 200 \\
\bottomrule
\end{tabular}
\caption{Messages per decision round. Snow's count is constant ($K \cdot \beta$) but high
per round; it requires multiple rounds for finality.}
\label{tab:messages}
\end{table}

\subsection{Quasar Message Breakdown}

Per committed block, Quasar exchanges:
\begin{itemize}
\item 1 block proposal broadcast (leader $\to$ all): $n$ messages
\item $n$ BLS partial signature responses (validators $\to$ leader): $n$ messages
\item 1 BLS aggregate broadcast (leader $\to$ all): integrated with next proposal
\item Pulsar shares collected in parallel: $n$ messages (piggybacked on BLS response)
\item 1 dual-certificate broadcast: integrated with next proposal
\end{itemize}

Total: $\approx 2n$ messages per block in steady state, yielding O($n$) complexity.
This is achieved by piggybacking Pulsar shares on the BLS vote message, avoiding a
separate collection round.

\subsection{Comparison with PBFT-family}

Tendermint inherits PBFT's all-to-all communication in the Prevote and
Precommit phases~\cite{tendermint}.
At $n{=}100$, each phase produces $100^2{=}10{,}000$ messages.
At $n{=}1{,}000$ this grows to $10^6$ messages per phase---the root
cause of Tendermint's scalability cliff (Section~\ref{sec:scalability}).

HotStuff~\cite{hotstuff} reduces this to O($n$) by funneling all votes through
the leader, which Quasar inherits. Quasar adds only a constant overhead
(${\sim}1.4{\times}$ HotStuff) for the Pulsar shares, since they are
piggybacked rather than sent separately.

%% ============================================================================