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.
37 lines
2.2 KiB
TeX
37 lines
2.2 KiB
TeX
\section{Conclusion}
|
|
|
|
\label{sec:conclusion}
|
|
|
|
We have presented the Wave protocol, a metastable consensus mechanism that achieves
|
|
decision stability through confidence monotonicity. The key innovation is the use of
|
|
cumulative confidence counters that track the full history of supermajority observations,
|
|
making decision reversal exponentially unlikely once a color establishes a lead.
|
|
|
|
Our formal analysis establishes three main results:
|
|
\begin{enumerate}[nosep]
|
|
\item Confidence monotonicity (Theorem~\ref{thm:monotonicity}): once color 1 leads by
|
|
$\delta$, the probability of reversal decays as $(q_0/q_1)^\delta$.
|
|
\item Exponential convergence (Theorem~\ref{thm:convergence}): the population fraction
|
|
converges to unanimity in $O(\log n)$ rounds.
|
|
\item DAG strong preference monotonicity (Theorem~\ref{thm:dag-monotone}): once a
|
|
transaction becomes strongly preferred in the DAG, it remains so with overwhelming
|
|
probability.
|
|
\end{enumerate}
|
|
|
|
Wave provides the theoretical foundation for the full Lux consensus protocol,
|
|
which builds the DAG-based transaction ordering and conflict resolution on top of
|
|
Wave's confidence mechanism.
|
|
|
|
\begin{thebibliography}{99}
|
|
\bibitem{castro1999practical} M. Castro and B. Liskov, ``Practical Byzantine fault tolerance,'' in \emph{OSDI}, 1999.
|
|
\bibitem{yin2019hotstuff} M. Yin et al., ``HotStuff: BFT consensus with linearity and responsiveness,'' in \emph{PODC}, 2019.
|
|
\bibitem{nakamoto2008bitcoin} S. Nakamoto, ``Bitcoin: A peer-to-peer electronic cash system,'' 2008.
|
|
\bibitem{rocket2019wave} T. Rocket et al., ``Scalable and probabilistic leaderless BFT consensus through metastability,'' 2019.
|
|
\bibitem{dwork1988consensus} C. Dwork, N. Lynch, and L. Stockmeyer, ``Consensus in the presence of partial synchrony,'' \emph{JACM}, 1988.
|
|
\bibitem{binder1987theory} K. Binder, ``Theory of first-order phase transitions,'' \emph{Reports on Progress in Physics}, 1987.
|
|
\bibitem{landau1980statistical} L. Landau and E. Lifshitz, \emph{Statistical Physics}, 3rd ed., Pergamon Press, 1980.
|
|
\bibitem{ising1925beitrag} E. Ising, ``Beitrag zur Theorie des Ferromagnetismus,'' \emph{Zeitschrift f\"ur Physik}, 1925.
|
|
\bibitem{glauber1963time} R. Glauber, ``Time-dependent statistics of the Ising model,'' \emph{J. Math. Phys.}, 1963.
|
|
\end{thebibliography}
|
|
|