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.
74 lines
3.1 KiB
TeX
74 lines
3.1 KiB
TeX
\section{Spectral Combiner}
|
|
|
|
\label{sec:combiner}
|
|
|
|
\subsection{Merging Band Outputs}
|
|
|
|
The spectral combiner produces a total order from the partial orders of each band.
|
|
|
|
\begin{definition}[Band Sequence]
|
|
Each band $b$ produces a sequence of finalized transactions $\sigma_b = (t_{b,1}, t_{b,2}, \ldots)$
|
|
in finalization order.
|
|
\end{definition}
|
|
|
|
\begin{definition}[Cross-Band Reference]
|
|
Transaction $t$ in band $b_1$ has a cross-band reference to band $b_2$ if $t$'s
|
|
execution depends on a transaction $t'$ finalized in band $b_2$. This creates a
|
|
causal dependency that the combiner must respect.
|
|
\end{definition}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Spectral Combiner --- Deterministic Merge}
|
|
\label{alg:combiner}
|
|
\begin{algorithmic}[1]
|
|
\Function{Combine}{$\sigma_0, \sigma_1, \ldots, \sigma_{B-1}$}
|
|
\State $\text{output} \gets []$; $\text{pos}[b] \gets 0$ for all $b$
|
|
\While{$\exists b : \text{pos}[b] < |\sigma_b|$}
|
|
\State \Comment{Select the band with smallest next timestamp}
|
|
\State $b^* \gets \arg\min_b \text{timestamp}(\sigma_b[\text{pos}[b]])$
|
|
\State $t \gets \sigma_{b^*}[\text{pos}[b^*]]$
|
|
\State \Comment{Check cross-band dependencies are satisfied}
|
|
\If{all cross-band references of $t$ are already in output}
|
|
\State Append $t$ to output; $\text{pos}[b^*] \gets \text{pos}[b^*] + 1$
|
|
\Else
|
|
\State \Comment{Dependency not yet satisfied: process the depended band first}
|
|
\State Process the depended band's next transaction first
|
|
\EndIf
|
|
\EndWhile
|
|
\State \Return output
|
|
\EndFunction
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{Order Consistency}
|
|
|
|
\begin{theorem}[Order Consistency]
|
|
\label{thm:order}
|
|
The spectral combiner produces a total order that:
|
|
\begin{enumerate}[nosep]
|
|
\item Respects the within-band order: if $t_1 <_b t_2$ in band $b$, then $t_1 <_{\text{total}} t_2$.
|
|
\item Respects cross-band dependencies: if $t_1$ references $t_2$, then $t_2 <_{\text{total}} t_1$.
|
|
\item Is deterministic: all honest validators produce the same total order.
|
|
\end{enumerate}
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
\textbf{(1)} The combiner processes each band's sequence in order, so within-band
|
|
ordering is preserved.
|
|
|
|
\textbf{(2)} Cross-band dependencies are resolved by the dependency check in the
|
|
algorithm: a transaction is only output after all its dependencies are satisfied.
|
|
Since each band's sequence is processed in order and dependencies point backward in
|
|
time (a transaction can only depend on previously finalized transactions), the dependency
|
|
graph is acyclic, and topological sorting is always possible.
|
|
|
|
\textbf{(3)} The combiner is deterministic given the band sequences $\sigma_b$.
|
|
All honest validators finalize the same transactions (by the safety of each band's
|
|
Photon instance), producing the same band sequences. The tie-breaking by timestamp
|
|
(with lexicographic band ordering for equal timestamps) ensures a unique total order.
|
|
\end{proof}
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 5. DIRECT VOTING FAST PATH
|
|
%% -----------------------------------------------------------------------
|