<p>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$.</p>

<p>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&gt;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 $&gt;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].</p>

<p>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.</p>

<p>[1] Ruggero, Bhattacharjee, Srinivasan, Marsh.
 Efficient lookup on unstructured topologies.</p>

CC BY-SA 3.0
2013-04-07T14:37:53.067Z
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.
Alain Jacomet Forte
CC BY-SA 3.0
2013-04-06T19:12:44.130Z
2013-04-07T16:25:44.790Z
2013-04-07T16:25:44.790Z
Peter
<p>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)?</p>

<dc.distributed-comp>
Distributed file storage system - theoretical approaches
Alain Jacomet Forte
# Distributed file storage system - theoretical approaches

(Asked by: username_0 on 2013-04-06)

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)?

**Tags:** dc.distributed-comp


---

## 1 answers

### Answer by username_1 on 2013-04-06. Score: 4

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.

> **Comments:**
> **username_0**: 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.  

---

