Set avoidance probabilities and bounds on the reliability of erasure coded storage systems

Bounds are developed on the probability that the Cartesian product of a given number of finite random sets does not intersect (avoids) a given fixed set. These bounds are then used to estimate the probability of data loss in a distributed storage system that uses erasure codes to protect against data loss when disks fail. These are the first bounds on the probability of data loss that we are aware of. We compare our upper bound on the probability of data loss to approximations that are used in the literature, and show that our bounds are tighter and the gap is significant in some cases. Our bounds also suggest that in some cases, a more efficient (higher rate) code will suffice to meet a data loss probability target than that predicted by approximations widely used in the industry.