Allocations for Heterogeneous Distributed Storage
The authors study the problem of storing a data object in a set of data nodes that fail independently with given probabilities. Their problem is a natural generalization of a homogenous storage allocation problem where all the nodes had the same reliability and is naturally motivated for peer-to-peer and cloud storage systems with different types of nodes. Assuming optimal erasure coding (MDS), the goal is to find a storage allocation (i.e., how much to store in each node) to maximize the probability of successful recovery. This problem turns out to be a challenging combinatorial optimization problem. In this paper, they introduce an approximation framework based on large deviation inequalities and convex optimization.