Optimal-availability placement of replicated data in distributed systems
D.M. Lazoff, A. B. Stephens · 2002
We investigate the problem of placing data in a distributed system in order to maximize data availability in the presence of network failures. In particular, we consider optimal placements of non-replicated and replicated data in networks with small probability of link failure. We show that an optimal location for non-replicated data must lie within a weighted median of the component tree composed of network bridges and 2-edge-connected components. We show that optimal placements of replicated data for read requests must allocate copies to the leaves of a k-tree core of the component tree. We show that optimal placements for write requests must be solutions to a packing optimization problem on the component tree.