Heuristic Algorithms for Replication Transition Problem in the Grid Systems

We study the replication transition problem (RTP) in the Grid systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to data access pattern, and a good strategy can improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another in order to cope with the dynamic data access pattern. This paper focuses on the RTP problem for Grid systems in four communication models that have different communication capabilities, i.e., whether message forwarding is allowed and whether network capacity is uniform among different links. We show that there exists a polynomial time algorithm that provides optimal solution for the RTP problem when forwarding is not allowed and the communication links are uniform. We also propose heuristic algorithms for solving variants of the RTP problem and conduct experiments to evaluate their performances. The experimental results indicate that our proposed heuristics are very effective.