A new model describing dependencies among system components as a directed graph is presented and used to solve a novel replica placement problem in data centers. A criterion for optimizing replica placements is formalized and explained. In this work, the optimization goal is to choose placements in which correlated failure events disable as few replicas as possible. A fast optimization algorithm is given for dependency models represented by trees. The main contribution of the paper is an O(n + ρ log ρ) dynamic programming algorithm for placing ρ replicas on a tree with n vertices.
展开▼
