Continuous replica placement schemes in distributed systems

Abstract

The Replica Placement Problem (RPP) aims at creating a set of duplicated data objects across the nodes of a distributed system in order to optimize certain criteria. Typically, RPP formulations fall into two categories: static and dynamic. The first assumes that access statistics are estimated in advance and remain static, and, therefore, a one-time replica distribution is sufficient (1RPP). In contrast, dynamic methods change the replicas in the network potentially upon every request. This paper proposes an alternative technique, named Continuous Replica Placement Problem (CRPP), which falls between the two extreme approaches. CRPP can be defined as: Given an already implemented replication scheme and estimated access statistics for the next time period, define a new replication scheme, subject to optimization criteria and constraints. As we show in the problem formulation, CRPP is different in that the existing heuristics in the literature cannot be used either statically or dynamically to solve the problem. In fact, even with the most careful design, their performance will be inferior since CRPP embeds a scheduling problem to facilitate the proposed mechanism. We provide insight on the intricacies of CRPP and propose various heuristics. Copyright 2005, ACM.