mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
42 lines
2.3 KiB
TeX
42 lines
2.3 KiB
TeX
\section{Introduction}
|
|
|
|
\label{sec:introduction}
|
|
|
|
Distributed consensus---the problem of achieving agreement among a set of processes in
|
|
the presence of failures---is foundational to replicated state machines, distributed
|
|
databases, and blockchain systems. Classical Byzantine fault tolerant (BFT) protocols
|
|
such as PBFT~\cite{castro1999practical} and HotStuff~\cite{yin2019hotstuff} achieve
|
|
deterministic safety under $f < n/3$ Byzantine faults but exhibit $O(n^2)$ or $O(n)$
|
|
communication complexity per decision, limiting scalability.
|
|
|
|
Nakamoto consensus~\cite{nakamoto2008bitcoin} scales to thousands of participants but
|
|
achieves only probabilistic safety that strengthens slowly over time, requiring minutes
|
|
to hours for practical finality. The metastable protocol family---Slush, Flare, Wave,
|
|
and Lux---introduced a fundamentally different paradigm: consensus through repeated
|
|
stochastic sampling, achieving $O(\log n)$ convergence with $O(kn)$ message complexity.
|
|
|
|
This paper formalizes the Wave protocol, the third member of the metastable family,
|
|
which introduces \emph{confidence counters} that track the full history of supermajority
|
|
observations. Unlike Flare's conviction counter (which tracks only consecutive rounds),
|
|
Wave's confidence counters are cumulative and monotone---once a color gains a lead,
|
|
the adversary must overcome the entire confidence history to reverse the decision.
|
|
|
|
\paragraph{Contributions.}
|
|
\begin{enumerate}[nosep]
|
|
\item A complete formal specification of the Wave protocol with DAG-based transaction
|
|
ordering and confidence counters (\S\ref{sec:protocol}).
|
|
\item A proof that confidence counters exhibit strict monotonicity under honest majority:
|
|
once color $c$ leads by margin $\delta$, the probability that a competing color catches
|
|
up decays exponentially in $\delta$ (\S\ref{sec:analysis}).
|
|
\item A Markov chain model of counter evolution yielding closed-form convergence bounds
|
|
(\S\ref{sec:markov}).
|
|
\item A proof that strong preference in the DAG is a monotone predicate under Wave
|
|
dynamics (\S\ref{sec:dag}).
|
|
\item Empirical evaluation on a 500-node testnet demonstrating sub-second finality
|
|
(\S\ref{sec:evaluation}).
|
|
\end{enumerate}
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 2. SYSTEM MODEL
|
|
%% -----------------------------------------------------------------------
|