What are the main theoretical approaches to a distributed file storage system that allows files to be stored across a network of nodes, assuring their availability in case a node randomly loses connection, but without replicating the entire tree in each node (as in git)?


A simple approach to achieve reliability and fast lookup in a "well connected" network $G$ is to replicate each file $f$ on a set $V_f$ of $\Theta(\sqrt{n}\log n)$ nodes and use random walks to efficiently find members of $V_f$.

When searching for a file $f$, we start $c\sqrt{n}\in \Theta(\sqrt{n})$ random walks of length $\tau$ from some particular node, where $\tau$ is the mixing time of a random walk on $G$. That is, after taking $\tau$ steps, a random walk has probability in $[1/2n,3/2n]$ of being at any particular node in $G$. Even if some $\epsilon\sqrt{n}\log n$ (for some small $\epsilon>0$) nodes have failed, the probability that at least one of these random walks encounters a node in $V_f$ is at least $$1-\left(1-\frac{\log n}{2\sqrt{n}}\right)^{c\sqrt{n}} \approx 1-\frac{1}{n^{c'}},$$ where $c'$ is a constant $>2$. Of course, this approach only makes sense if $\tau$ is sufficiently small - that's what I meant above when saying "well connected" network. This is the case in networks with sufficiently large (i.e. constant) spectral gap since $\tau \in O(\log n)$. A similar approach is taken in [1].

After some time, most of the $\Theta(\sqrt{n}\log n)$ could have been removed. Thus it is necessary to estimate the current size of $V_f$ periodically and replenish the removed members of $V_f$ by replicating $f$ on new nodes.

[1] Ruggero, Bhattacharjee, Srinivasan, Marsh. Efficient lookup on unstructured topologies.

  • $\begingroup$ Excellent and straightforward answer. I would mark it as definitive but I'm looking for an overview of the existing different approaches rather than just one effective one. Please still keep the answer posted. $\endgroup$ – Alain Jacomet Forte Apr 7 '13 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.