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.
59 lines
2.2 KiB
TeX
59 lines
2.2 KiB
TeX
\section{The Nebula Protocol}
|
|
|
|
\label{sec:protocol}
|
|
|
|
\subsection{Stratified Sampling}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Nebula Protocol --- Stratified Neighborhood Sampling}
|
|
\label{alg:nebula-core}
|
|
\begin{algorithmic}[1]
|
|
\Require Validator $v$, transaction $t$, neighborhood $\mathcal{N}(v)$
|
|
\Require Parameters: $k$ (sample size), $\alpha$ (quorum), $\beta$ (threshold), $k_b$ (bridge queries)
|
|
\State $d_c \gets 0$ for all colors $c$
|
|
\While{$\max_c d_c < \beta$}
|
|
\State \Comment{Phase 1: Local sampling within neighborhood}
|
|
\State $S_L \gets \text{RandomSample}(\mathcal{N}(v), k - k_b)$
|
|
\State \Comment{Phase 2: Bridge sampling for cross-neighborhood information}
|
|
\State $B \gets \text{SelectBridges}(v, k_b)$ \Comment{select $k_b$ bridges to distant neighborhoods}
|
|
\State $S \gets S_L \cup B$ \Comment{combined sample}
|
|
\State Query each $u \in S$ for $\text{col}(u, t)$
|
|
\For{each color $c$}
|
|
\State $n_c \gets |\{u \in S : \text{col}(u, t) = c\}|$
|
|
\If{$n_c \geq \alpha k$}
|
|
\State $d_c \gets d_c + 1$
|
|
\EndIf
|
|
\EndFor
|
|
\State $\text{col}(v, t) \gets \arg\max_c d_c$
|
|
\If{$\max_c d_c \geq \beta$}
|
|
\State \textbf{finalize} $t$ with color $\arg\max_c d_c$
|
|
\EndIf
|
|
\EndWhile
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{Bridge Selection}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Nebula Bridge Selection}
|
|
\label{alg:nebula-bridge}
|
|
\begin{algorithmic}[1]
|
|
\Function{SelectBridges}{$v$, $k_b$}
|
|
\State $\text{bridges} \gets \emptyset$
|
|
\State \Comment{Select validators that connect to distant neighborhoods}
|
|
\For{$i = 1$ to $k_b$}
|
|
\State $u \gets$ random validator from $\mathcal{N}(v)$ maximizing $\min_{b \in \text{bridges}} \|u - b\|$
|
|
\State $\text{bridges} \gets \text{bridges} \cup \{u\}$
|
|
\EndFor
|
|
\State \Return bridges
|
|
\EndFunction
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
The bridge selection ensures that the $k_b$ bridge validators are spread across
|
|
the neighborhood boundary, maximizing the information gathered from distant regions.
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 4. CONVERGENCE ANALYSIS
|
|
%% -----------------------------------------------------------------------
|