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.
38 lines
3.2 KiB
TeX
38 lines
3.2 KiB
TeX
\section{Introduction}
|
|
|
|
|
|
The fundamental challenge in distributed consensus is achieving agreement among nodes in the presence of Byzantine failures while maintaining both safety and liveness properties. Traditional deterministic consensus protocols such as PBFT~\cite{castro1999practical} and HotStuff~\cite{yin2019hotstuff} provide absolute safety guarantees but suffer from $O(n^2)$ or $O(n)$ message complexity, limiting their scalability.
|
|
|
|
Probabilistic consensus protocols offer an alternative approach by trading a negligible probability of disagreement for significant performance improvements. The key insight is that by accepting a safety violation probability of $< 0.001\%$, we can reduce message complexity to $O(k \log n)$ where $k \ll n$ is a small committee size.
|
|
|
|
\subsection{Motivation}
|
|
|
|
The need for adaptive thresholds in probabilistic consensus arises from several observations:
|
|
|
|
\begin{enumerate}
|
|
\item \textbf{Metastability}: Fixed voting thresholds can cause the network to oscillate between opinions without reaching consensus, particularly when the initial opinion distribution is close to the threshold.
|
|
|
|
\item \textbf{Exploration vs. Exploitation}: Early rounds should explore the opinion space to discover the true majority, while later rounds should lock in the decision to ensure termination.
|
|
|
|
\item \textbf{Byzantine Resilience}: Adaptive thresholds make it harder for Byzantine nodes to predict and manipulate voting outcomes across rounds.
|
|
|
|
\item \textbf{Network Conditions}: Different network partitions and latency distributions require different convergence strategies.
|
|
\end{enumerate}
|
|
|
|
\subsection{Contributions}
|
|
|
|
This paper makes the following contributions:
|
|
|
|
\begin{itemize}
|
|
\item We formalize the Fast Probabilistic Consensus (FPC) protocol with rigorous safety and liveness proofs, verified in Lean~4 with machine-checked proofs~\cite{luxformal2025}.
|
|
\item We introduce a sigmoid cooling function for adaptive threshold computation that prevents metastability.
|
|
\item We present ZAP (Zero-copy Application Protocol), a binary wire format that achieves $14\times$ deserialization improvement over Protobuf for consensus messages.
|
|
\item We provide a complete implementation integrated with the Lux blockchain consensus stack.
|
|
\item We demonstrate through extensive simulations that FPC achieves sub-second finality at global scale.
|
|
\end{itemize}
|
|
|
|
\subsection{Paper Organization}
|
|
|
|
Section~\ref{sec:architecture} describes how FPC fits within the Lux consensus architecture. Section~\ref{sec:algorithm} presents the core FPC algorithm. Section~\ref{sec:adaptive} details the adaptive threshold mechanism. Sections~\ref{sec:threshold} through~\ref{sec:termination} cover technical components. Section~\ref{sec:security} provides security analysis. Section~\ref{sec:performance} presents performance characteristics. Section~\ref{sec:comparison} compares FPC with other protocols. Sections~\ref{sec:integration} and~\ref{sec:simulation} discuss integration and simulation results. Section~\ref{sec:zap} presents the ZAP zero-copy wire format and its throughput impact. Section~\ref{sec:formal} details the Lean~4 formal verification of FPC's core properties. Section~\ref{sec:conclusion} concludes.
|
|
|