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.
73 lines
2.8 KiB
TeX
73 lines
2.8 KiB
TeX
\section{FPC Algorithm}
|
|
|
|
\label{sec:algorithm}
|
|
|
|
The Fast Probabilistic Consensus protocol achieves agreement through iterative voting rounds with random committee sampling.
|
|
|
|
\subsection{Core Protocol}
|
|
|
|
\begin{definition}[$\varepsilon$-consensus]
|
|
A protocol achieves $\varepsilon$-consensus if all honest nodes agree on the same value with probability at least $1 - \varepsilon$.
|
|
\end{definition}
|
|
|
|
\begin{definition}[Phase Function]
|
|
A phase function $\varphi: \mathbb{N} \to [0.5, 1]$ determines the decision threshold at round $r$.
|
|
\end{definition}
|
|
|
|
\begin{algorithm}
|
|
\caption{Fast Probabilistic Consensus}
|
|
\label{alg:fpc}
|
|
\begin{algorithmic}[1]
|
|
\REQUIRE Transaction $tx$, parameters $(k, \beta, \theta_{\min}, \theta_{\max})$
|
|
\ENSURE Opinion $\in \{\text{true}, \text{false}\}$ with confidence $c$
|
|
\STATE $\text{opinion} \gets \text{initialOpinion}(tx)$
|
|
\STATE $\text{consecutiveAgreements} \gets 0$
|
|
\STATE $\text{temperature} \gets 1.0$
|
|
\FOR{$r = 0$ to $\text{maxRounds}$}
|
|
\STATE $\theta \gets \text{computeThreshold}(r, \text{temperature})$
|
|
\STATE $\text{committee} \gets \text{randomSample}(k)$
|
|
\STATE $\text{responses} \gets \text{queryNodes}(\text{committee}, tx)$
|
|
\STATE $\text{positive} \gets \sum_{i} \mathbb{1}[\text{responses}[i] = \text{true}]$
|
|
\STATE $\text{ratio} \gets \text{positive} / |\text{responses}|$
|
|
\STATE $\text{newOpinion} \gets (\text{ratio} > \theta)$
|
|
\IF{$\text{newOpinion} = \text{opinion}$}
|
|
\STATE $\text{consecutiveAgreements} \gets \text{consecutiveAgreements} + 1$
|
|
\IF{$\text{consecutiveAgreements} \geq \beta$}
|
|
\STATE \textbf{return} $(\text{opinion}, \text{confidence}(r, \beta))$
|
|
\ENDIF
|
|
\ELSE
|
|
\STATE $\text{opinion} \gets \text{newOpinion}$
|
|
\STATE $\text{consecutiveAgreements} \gets 1$
|
|
\ENDIF
|
|
\STATE $\text{temperature} \gets \text{temperature} \times \text{coolingRate}$
|
|
\ENDFOR
|
|
\STATE \textbf{return} $(\text{opinion}, \text{lowConfidence})$
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{Safety and Liveness}
|
|
|
|
\begin{theorem}[FPC Safety]
|
|
\label{thm:safety}
|
|
FPC achieves $\varepsilon$-consensus with $\varepsilon = 2^{-\lambda}$ where $\lambda = \beta \cdot k \cdot (\theta - 0.5)^2$ for $\beta$ consecutive rounds of agreement, $k$ samples, and threshold $\theta$.
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
Let $X_i$ be the indicator that round $i$ achieves supermajority. For honest majority $h > 0.5$:
|
|
\begin{align}
|
|
P(X_i = 1 \mid \text{honest preference}) &\geq P(\text{Binomial}(k, h) > \theta) \\
|
|
&> 1 - e^{-2k(h-\theta)^2} \quad \text{(Chernoff bound)}
|
|
\end{align}
|
|
|
|
After $\beta$ rounds of agreement:
|
|
\begin{align}
|
|
P(\text{consensus}) &\geq \left(1 - e^{-2k(h-\theta)^2}\right)^\beta
|
|
\end{align}
|
|
|
|
With typical parameters $k = 20$, $\theta = 0.67$, $\beta = 3$:
|
|
\begin{align}
|
|
P(\text{consensus}) > 0.99999
|
|
\end{align}
|
|
\end{proof}
|
|
|