The complexity of static data replication in data grids

Data replication is a well-known technique used in distributed computing to improve access to data and/or system fault-tolerance. Recently, studies of its applications to grid computing have also been initiated. In this article we describe data replication on data grids as a static optimization problem. We show that this problem is NP-hard and non-approximable. We discuss two approaches to solving it, i.e. integer programming and simplifications.