Dynamic data replication for distributed cloud storage

Abstract

Cloud storage services have become increasingly popular in recent years. This thesis investigates a cost optimization problem for data replication in distributed cloud storage. We consider two different settings: offine and online. In the offine setting where the complete information of data access requests is available, we develop an O(max(m^2n, n^2)) optimal algorithm, where m and n are the numbers of storage sites and requests respectively. In the online setting where the requests arriving in the future are not known, we propose two distributed algorithms: a 3-competitive basic algorithm and a dynamic algorithm. Both algorithms are lightweight and easy to implement. Experiments using the pricing data of Google Cloud Storage show that our online algorithms can perform close to the optimal.