Formal model and scheduling heuristics for the replica migration problem

Abstract

Replication of the most popular objects is often used in distributed data provision systems to reduce access time and improve availability. In fact, a given replica placement scheme may have to be redefined as object popularity changes. Given two replica placement schemes X old and X new , the Replica Migration Problem (RMP) is to compute a schedule of replica transfers and deletions that lead from X old to X new in the shortest time possible. In this paper, we provide a rigorous problem formulation and prove that even for trivial cases RMP is intractable. We also propose a set of heuristics and evaluate them for different scenarios using simulations. © 2008 Springer-Verlag Berlin Heidelberg.