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.
53 lines
2.0 KiB
TeX
53 lines
2.0 KiB
TeX
\section{The Photon Protocol}
|
|
|
|
\label{sec:protocol}
|
|
|
|
\subsection{Pipelined Sampling}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Photon Protocol --- Pipelined Consensus}
|
|
\label{alg:photon-core}
|
|
\begin{algorithmic}[1]
|
|
\Require Validator $v$, pipeline depth $m$
|
|
\Require Parameters: $k$ (sample size), $\alpha$ (quorum), $\beta$ (threshold)
|
|
\State $\text{pipeline}[] \gets$ array of $m$ slots, initially empty
|
|
\Loop
|
|
\State \Comment{Fill empty slots with pending transactions}
|
|
\For{each empty slot $s$}
|
|
\If{$\exists$ pending transaction $t_s$}
|
|
\State $\text{pipeline}[s] \gets t_s$; $D_{s,c} \gets 0$ for all $c$
|
|
\EndIf
|
|
\EndFor
|
|
\State $S \gets \text{RandomSample}(V \setminus \{v\}, k)$
|
|
\State \Comment{Batch query: ask for all pipeline transactions at once}
|
|
\State Query each $u \in S$ for $\{\text{col}(u, t_s) : s \in \text{active slots}\}$
|
|
\For{each active slot $s$ with transaction $t_s$}
|
|
\For{each color $c$}
|
|
\State $n_c \gets |\{u \in S : \text{col}(u, t_s) = c\}|$
|
|
\If{$n_c \geq \alpha k$}
|
|
\State $D_{s,c} \gets D_{s,c} + 1$
|
|
\EndIf
|
|
\EndFor
|
|
\State $\text{col}(v, t_s) \gets \arg\max_c D_{s,c}$
|
|
\If{$\max_c D_{s,c} \geq \beta$}
|
|
\State \textbf{finalize} $t_s$ with color $\arg\max_c D_{s,c}$
|
|
\State Free slot $s$
|
|
\EndIf
|
|
\EndFor
|
|
\EndLoop
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{Message Format}
|
|
|
|
Each query message carries a vector of $m$ transaction identifiers, and each response
|
|
carries a vector of $m$ color preferences. The message overhead compared to single-transaction
|
|
queries is $O(m)$ per message, resulting in amortized $O(1)$ per transaction per round.
|
|
|
|
For $m = 100$ transactions and 32-byte transaction IDs + 1-byte color each, the query
|
|
overhead is $100 \times 33 = 3.3$KB, well within typical UDP datagram limits.
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 4. SAFETY ANALYSIS
|
|
%% -----------------------------------------------------------------------
|