The Assumptions for Durability under Altruism

Durability hinges on making a quantifiable assumption about how likely it is that a storage provider will hold on to the data it has been assigned to, and is currently helping maintain.

Data enters our system as files; i.e., named byte strings of variable size. Let be the set of all such possible files. Let be the set of all nodes in our network, across its existence. We assume time to be a real-valued, positive-or-zero value , with marking the inception of the system.

To make this discussion simpler, we can assume that:

1. any file enters our system by being initially replicated onto a set of nodes ;
2. there is no repair.

One way of quantifying durability for , then, is by attempting to assign a probability density function to each node , such that represents the probability that has dropped by time . To simplify notation, we will omit and write those simply as and .

Assuming that these probabilities are independent across nodes, we can compute the cumulative probability for being lost by time as:

Optimization of loss. Our “number of nines” for at time is given by . It should be clear, then, that a storage system should always try to build (or induce) an which minimizes such loss. This involves making assumptions about which can be pure assumptions, or the result of measurement.

Repair. Eq. makes the simplifying assumption of no repair, and it does not hold when repair is in place as could “grow back” as a result of repair actions. The fundamental fact that durability hinges on the assumptions built into , however, would not change — we would simply need to add an additional set of assumptions as to what we believe the probabilities of finding new nodes to replace the failed one are.

Cryptoeconomical durability. For old Codex, our analysis of durability¹ took into consideration hardware faults only, and used exponentially-distributed calibrated on data taken from studies of faults in data center hard drives.²

This is a fair assumption if we also assume that slashing costs are enough to eliminate data loss from both churn³ — as slashing functions as an uptime incentive — and arbitrary provider choice, as no provider would rationally decide to deliberately drop data and inflict monetary loss upon itself. But this again assumes that the token holds enough value to make slashing hurt: if that last assumption does not hold, then the durability numbers become meaningless.

A more honest approach would be to model this loss-of-value event; i.e., define as the probability that the Codex tokens loses enough value by time such that:

1. is operating at loss;
2. the slashing cost for , should it drop , is lower than the loss it would incur if it honored the storage contract to conclusion.

In such case, it would be reasonable to expect that would drop the data. If we now name the probability of data loss happening due to hardware faults as , the new aggregate loss probability (assuming and are independent) then becomes:

is unfortunately much harder to eastimate than , so we simply never did that. It should be clear that it is an integral part of durability, and a blind spot in our model. What about altruistic Codex? What can we say about it?

The Stable Intrinsic Interest Model

In altruism there is no cryptoeconomic incentive mechanism, so is not a part of our model, and we are free from having to estimate it. As to what comes in its place, there are a few different assumptions we can make here, and they all result in different outcomes for durability, as well as potentially different designs for our system. One assumption which we would like to discuss here is what we refer to as the Stable Intrinsic Interest (SII) model.

In SII, we assume the existence of a set which expresses node’s interests, and we assume that :

1. is only willing store files in ;
2. is willing to store such data forever; i.e., interest is stable.

This is roughly equivalent to stating that, based on interest, the probability that a node drops data by time :

This means that, under SII, reduces to:

One of the appeals of SII is its simplicity: we do not have to estimate anything else to compute our durability numbers. Indeed, it reduces precisely to the same analysis we did for old Codex, which is one of the reasons I do not like calling it “low durability”.

Maximal durability in SII. Eq. and (4) taken together mean that we want:

1. an that is as big as possible, as is monotonically nonincreasing on ;
2. nodes such that , as other nodes will not positively impact durability.

Those are both obvious and intuitive statements, but they also have a somewhat less clear implication. Namely, that node will likely need to know what the content of is before it can decide whether or not it is interested in it. Blindly offering content on the network for replication, therefore, is unlikely to be a successful strategy under SII.

Communities instead of files. Instead of modeling as a subset of , one could instead imagine that nodes form communities, and that represents the set of communities a node participates in. This is likely an assumption we will be making for Codex.

Altruism and Churn

In cryptoeconomic durability, nodes must remain running so they can reply to remote audit requests that come in at random instants in time. Since bringing one’s node down is a gamble that could result in slashing, this curbs churn.

Under altruistic models like SII, these incentives no longer exist. Unless we further assume that operators are intrinsically motivated to keep their nodes running, this means we now need to deal with churn.

The cautionary tale for the cost of active repair under churn is provided in Blake and Rodrigues classical paper.⁴ How much of a problem this turns out to be in practice largely depends on how we envision the system to work.

Blake and Rodrigues’ model assumes a constant turnover of new nodes, which might not be realistic. Let represent the set of all nodes, across the network’s lifetime, that would be willing to store . We assume to be finite, and likely much smaller than . We also assume that altruistic storage nodes, as much as they might not be always available, will not delete the data they hold on every logoff.

Replication. In SII under replication, every repair operation entails:

1. picking a node in that is currently available;
2. getting it to download and store it.

If we assume nodes do not delete data on logoff, then it should be clear that the number of repair operations is bounded by . Once repair operations happen, should be fully replicated across all nodes in the , which is the worst case for active repair.

Erasure coding. Erasure coding makes things more complicated as the sets of blocks nodes hold are, perhaps surprisingly, not fungible. Suppose for simplicity that is erasure coded with -out-of- redundancy into blocks such that any blocks are enough to reconstitute , and such that blocks are spread onto different nodes.

Every time a block , , disappears from the network, we need to ensure that it gets recreated, and this repair operation requires the download of blocks; i.e., it has the same bandwidth cost as that of restoring a replica. If nodes do not throw that data away (or lose it) after repair, erasure-coding then degenerates into full replication in the worst case (assuming is finite).

If they do throw away the data, then things get even worse as nodes might be selected for repair repeatedly, leading to bandwidth costs per repair round. This would likely approximate the more pessimistic costs of Blake and Rodrigues.⁴

Before going about implementing complicated replica tracking and repair mechanisms, therefore, I believe we should carefully consider what sort of network dynamics we should expect, particularly in the absence of uptime incentives.

Footnotes

1. Codex Team, “Codex Whitepaper”. https://docs.codex.storage/learn/whitepaper ↩

2. B. Schroeder and G. A. Gibson, “Disk Failures in the Real World: What Does an MTTF of 1,000,000 Hours Mean to You?,” in Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST ‘07), San Jose, CA, USA, 2007 ↩

3. Which are not real “faults” in the sense that nodes might be crash-recover in the real world, but since we cannot distinguish that from real data loss we typically assume that nodes that stop providing heartbeats have lost their replica or erasure-coded partition permanently. ↩

4. C. Blake and R. Rodrigues. 2003. High availability, scalable storage, dynamic peer networks: pick two. In Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9 (HOTOS’03). USENIX Association, USA, 1. ↩ ↩²