Considerations on "Low Durability"

# Considerations on "Low Durability" ## Best-Effort Durability We have been discussing a "low durability" mode for Codex and putting together mechanisms for it. I feel the need to understand what this is aiming for from a more principled perspective. As in: * what properties are we aiming for? * Under which assumptions should those properties hold/not hold? First, I do not think "low durability" is a good name -- the original Codex could also provide "low durability" depending on parameters, and the durability you get from an altruistic system does not have to be low. I am therefore referring to this here as _best-effort_ durability. Ideally, the property I would like from best-effort durability is that durability is conditioned on storage provider willingness to hold data. Let us try to characterize this. Let $D_t$ be the set of nodes in our network at time $t \in \mathbb{Z}^{+}$. Let $q \in D_t$ be a network participant wishing to persist a file $F$. We assume there is a set $W_t \subseteq D$ of storage providers in the network, including $q$, that are _willing_ to hold a copy[^1] of $F$ on behalf of $q$ to prevent if from disappearing. Let $S_t \subseteq W_t$ be the _actual set_ of nodes holding $F$ at time $t$. **Definition 1.** We say that $F$ has been _lost_ at time instant $a$ iff $S_a = \emptyset$.[^3] I can then try to characterize what I would like from best-effort durability as: **Property 1.** $F$ should be lost iff there exists a time instant $a$ such that $W_t = \emptyset$. In other words, for as long as there are nodes willing to hold $F$, we would like our system to guarantee that it does not disappear.[^2] A (perhaps) surprising fact, then, is is: **Corollary 1.** Bittorrent provides best-effort durability. In Bittorrent, nodes interested in storing a file $F$ join its swarm and replicate it. As long as the swarm is not empty (i.e., $W_t \neq 0$), $F$ does not disappear. Bittorrent therefore provides best-effort durability. My question, then, is what are we _really_ adding with our much more complex, "low durability" mode? ## "Low Durability" Mode vs BitTorrent Bittorrent replication is based on _explicit interest_; i.e., if a node _wants_ to replicate a given dataset, it needs to explicitly join its swarm. I would argue that this fits well with many of the altruistic use cases we have had presented to us; e.g.: 1. if I am an activist and I want to keep a whistleblower archive online, I can simply join the swarm for each of the archives and replicate them; 2. if I am a member of a community and I want to make sure that the message archives in it remain available, I simply join its swarm. Bittorrent's main shortcomings here relate to _privacy_ -- you cannot hide that you are participating in a swarm -- and _discoverability_ -- you are assumed to learn about which CIDs you want to replicate "somehow". And this has an important implication as to how one wold maintain Property 1: intuitively, for things to work, we need to have $S_t \sim W_t$ for all $t$ (sets could diverge slightly during handoff or repair but they should be always close to each other). This means that all nodes in $W_t$ must know, at all times, the CID for the files they are willing to hold. We, on the other hand, are proposing a very different system. What problems does it solve? **Discoverability.** CIDs are pushed over the network from publishers to $W_t$, so they do not need an out-of-band mechanism to learn it (e.g. piratebay).  **Storage efficiency.** "Low-durability" mode attempts to cap the number of replicas. This adds a bound to $|S_t|$, and saves space in the $W_t$ so they can dedicate it to other files. **Load balancing.** If we always manage to randomize properly across $W_t$, then storage utilization should converge onto the average file size for all storage providers once they store a large enough set of files each. **Controllable durability.** Although we call this "low durability", the fact that there is a tunable bound in $|S_t|$ means that durability might be actually quite high. The actual durability is contingent on the loss probabilities we put on each replica. If those are uniform, then the actual analysis of durability is the _same_ as we had for "high durability" Codex. [^1]: Let us make it simple and start with replication. [^2]: In practice we would need to refine this as copies and repair are not instantaneous, so you could still have a non-empty set and loss if that set changes faster than you can repair. [^3]: Note that this is a very pessimistic definition of loss -- a participant could leave the network and _not_ delete the data, then re-join later on -- but as observers we cannot ever distinguish between temporary and permanent departures (loss), so this is the best we can do. "Old Codex" also made this assumption. [^5]: Does Freenet satisfy all of those requirements?