mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
1ecc25e9cf
The seven engine specifications (lux-{photon,wave,nova,nebula,prism,ray,field}-protocol)
were fragmented short notes documenting layers of the same Quasar consensus stack.
This commit merges them into a single canonical reference, lux-consensus-engines.tex,
that uses one preamble, one set of theorems, one bibliography, and one composition
chapter showing how the engines layer into the LP-020 finality pipeline.
The seven originals are reduced to single-page breadcrumb stubs pointing at the
consolidated paper; their sections/ content is preserved on disk for git history.
- new: lux-consensus-engines/ (50 pages, 646KB PDF, ~2900 lines tex)
- breadcrumbs: each original keeps cover + title + stub paragraph naming its chapter
- composition: chapter 9 records the layered contract Photon < Wave < Nova < ...
- bibliography: consolidated from the seven original thebibliography blocks
42 lines
2.3 KiB
TeX
42 lines
2.3 KiB
TeX
\section{Introduction}
|
|
|
|
\label{sec:wave-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:wave-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:wave-analysis}).
|
|
\item A Markov chain model of counter evolution yielding closed-form convergence bounds
|
|
(\S\ref{sec:wave-markov}).
|
|
\item A proof that strong preference in the DAG is a monotone predicate under Wave
|
|
dynamics (\S\ref{sec:wave-dag}).
|
|
\item Empirical evaluation on a 500-node testnet demonstrating sub-second finality
|
|
(\S\ref{sec:wave-evaluation}).
|
|
\end{enumerate}
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 2. SYSTEM MODEL
|
|
%% -----------------------------------------------------------------------
|