papers/lux-state-sync/sections/07-multi-source-download.tex

\section{Multi-Source Download}
\label{sec:multisource}

\subsection{Peer Selection}

The syncing node maintains a peer set $\mathcal{P}$ and assigns chunks to peers based on availability and latency:

\begin{algorithm}[H]
\caption{Multi-Source Chunk Assignment}
\label{alg:multisource}
\begin{algorithmic}[1]
\Require Chunks $\mathcal{C}$, peers $\mathcal{P}$, max parallelism $P$
\State $\mathsf{queue} \gets \mathcal{C}$ (priority queue by chunk size descending)
\State $\mathsf{active} \gets \emptyset$ (active downloads, max $P$)
\While{$\mathsf{queue} \neq \emptyset$ or $\mathsf{active} \neq \emptyset$}
    \While{$|\mathsf{active}| < P$ and $\mathsf{queue} \neq \emptyset$}
        \State $c \gets \mathsf{queue}.\mathsf{pop}()$
        \State $p \gets \arg\min_{p' \in \mathcal{P}} \mathsf{latency}(p')$
        \State Start download of $c$ from $p$; add to $\mathsf{active}$
    \EndWhile
    \State Wait for any download to complete
    \State $(c, data, \pi, p) \gets$ completed download
    \If{$\mathsf{VerifyChunk}(data, \pi, R)$}
        \State Write to database
    \Else
        \State $\mathsf{queue}.\mathsf{push}(c)$; penalize $p$
    \EndIf
    \State Remove from $\mathsf{active}$
\EndWhile
\end{algorithmic}
\end{algorithm}

\subsection{Adversarial Peer Resilience}

\begin{theorem}[Sync Liveness Under Adversary]
If at least one honest peer with the target state is reachable, state sync completes in bounded time despite adversarial peers providing invalid data.
\end{theorem}

\begin{proof}
Invalid chunks fail verification (Algorithm~\ref{alg:verify_range}) and are re-queued for download from different peers. Adversarial peers are penalized and eventually banned. The syncing node retries each chunk until receiving valid data from an honest peer. Since the chunk set is finite, sync completes in at most $|\mathcal{C}| \cdot |\mathcal{P}|$ attempts in the worst case.
\end{proof}

\subsection{Bandwidth Optimization}

\begin{proposition}[Bandwidth Overhead]
The total bandwidth for state sync is:
\begin{equation}
    B_{\text{total}} = S + |\mathcal{C}| \cdot 2d \cdot N_{\text{avg}} + O(|\mathcal{C}| \cdot d \cdot 32)
\end{equation}
where $S$ is the raw state size. The proof overhead is bounded by:
\begin{equation}
    \text{Overhead} = \frac{B_{\text{total}} - S}{S} \leq \frac{2d \cdot N_{\text{avg}}}{S_{\text{target}}} \approx \frac{2 \cdot 8 \cdot 550}{4{,}000{,}000} \approx 0.22\%
\end{equation}
\end{proposition}