# Distributed file storage system - theoretical approaches

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.