title: Calculating the probability of system failure in a distributed network
body: <p>I am trying to build a mathematical model of the availability of a file in a distributed file-system. I posted this question at MathOverflow but this might as well be classified as a CS-question so I give it a shot here as well.</p>
  <p>The system works like this: a node stores a file (encoed using erasure codes) at r*b remotes nodes, where r is the replication-factor and b is an integer constant. Erasure-coded files have the property that the file can be restored iff at least b of the remote nodes are available and return its part of the file.</p>
  <p>The simplest approach to this is to assume that all remote nodes are independent of each other and have the same availability p. With these assumptions the availability of a file follows the Binomial distribution, i.e. <img src="https://latex.codecogs.com/png.latex?pf%20=%20%5Csum_%7Bi=b%7D%5E%7Brb%7D%20%5Cbinom%7Brb%7D%7Bi%7D%20p%5Ei%281%20-%20p%29%5E%7Brb%20-%20i%7D$" alt="Binomial distribution" /></p>
  <p>Unfortunately these two assumptions can introduce a non-neligible error, as shown by this paper: <a href="http://deim.urv.cat/%7Elluis.pamies/uploads/Main/icpp09-paper.pdf" rel="nofollow noreferrer">http://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf</a>.</p>
  <p>One way to overcome the assumption that all nodes have the same availability is to calculate the probability of each possible combination of availaible/non-available node and take the sum of all these outcomes (which is sort of what they suggest in the paper above, just more formally than what I just described). You can see this approach as a binary tree with depth r*b and each leave is one possible combination of available/not-available nodes. The file's availability is the same thing as the probablity that you arrive at a leave with &gt;=b available nodes. This approach is more correct but has a computational cost of <a href="https://i.stack.imgur.com/LlZyG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LlZyG.png" alt="Ordo" /></a>. Also, it doesn't deal with the assumption of node independence.</p>
  <p>Do you guys have any ideas of a good approximation which introduces less error than the binomial distribution-aproximation but with better computational cost than <a href="https://i.stack.imgur.com/LlZyG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LlZyG.png" alt="" /></a>?</p>
  <p>You can assume that the availability-data of each node is a set of tuples consisting of <code>(measurement-date, node measuring, node being measured, succes/failure-bit)</code>. With this data you could for example calculate the correlation of the availability between the nodes and the availability variance.</p>