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.
48 lines
2.0 KiB
TeX
48 lines
2.0 KiB
TeX
\section{Hierarchical Chunking}
|
|
\label{sec:chunking}
|
|
|
|
\subsection{Chunk Definition}
|
|
|
|
Rather than fixed-size byte chunks, we align chunks to trie node boundaries:
|
|
|
|
\begin{definition}[Trie-Aligned Chunk]
|
|
A chunk $c = (p, d_c)$ is defined by a trie path prefix $p$ and depth $d_c$. It encompasses all leaves whose keys start with prefix $p$, and includes all trie nodes in the subtree rooted at the node addressed by $p$.
|
|
\end{definition}
|
|
|
|
\subsection{Chunk Planning}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Hierarchical Chunk Planning}
|
|
\label{alg:plan}
|
|
\begin{algorithmic}[1]
|
|
\Require Root $R$, target chunk size $S_{\text{target}}$
|
|
\Ensure Set of chunks $\mathcal{C}$ covering entire state
|
|
\State Request top $d_{\text{plan}}$ levels of trie from peer
|
|
\State $\mathcal{C} \gets \emptyset$
|
|
\For{each subtree $T$ at depth $d_{\text{plan}}$}
|
|
\State $s_T \gets$ estimated size of $T$ (from node counts)
|
|
\If{$s_T \leq S_{\text{target}}$}
|
|
\State $\mathcal{C} \gets \mathcal{C} \cup \{T\}$ \Comment{$T$ is one chunk}
|
|
\Else
|
|
\State Recursively split $T$ into sub-chunks
|
|
\EndIf
|
|
\EndFor
|
|
\State \Return $\mathcal{C}$
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
With $S_{\text{target}} = 4$ MB and 42 GB total state, we get approximately 10,500 chunks. At 16 parallel downloads, this yields $\approx 660$ sequential rounds, each transferring 64 MB.
|
|
|
|
\subsection{Optimal Parallelism}
|
|
|
|
\begin{proposition}[Download Time Lower Bound]
|
|
With bandwidth $B$ (bytes/sec), $P$ parallel connections, and total state size $S$:
|
|
\begin{equation}
|
|
T_{\min} = \frac{S}{B \cdot P} + \frac{S}{S_{\text{target}}} \cdot \Delta_{\text{RTT}}
|
|
\end{equation}
|
|
where $\Delta_{\text{RTT}}$ is the round-trip time for chunk requests.
|
|
\end{proposition}
|
|
|
|
For $S = 42$ GB, $B = 12.5$ MB/s (100 Mbps), $P = 16$, $S_{\text{target}} = 4$ MB, $\Delta_{\text{RTT}} = 100$ ms: $T_{\min} = 215\text{s} + 1{,}050\text{s} \cdot 100\text{ms}/P \approx 215 + 6.6 = 222$ seconds $\approx 3.7$ minutes. In practice, verification overhead and retries increase this to 15--30 minutes.
|
|
|