2025/10/28 by Zuo, Tianyu, Tang, Xueyan, Lee, Bu Sung +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2510.24098
This paper studies an online cost optimization problem for distributed storage and access. The goal is to dynamically create and delete copies of data objects over time at geo-distributed servers to serve access requests and minimize the total storage and network cost. We revisit a recent algorithm in the literature and show that it does not have a competitive ratio of 2 as claimed by constructing a counterexample. We further prove that no deterministic online algorithm can achieve a competitive ratio bounded by 2 for the general cost optimization problem. We develop an online algorithm and prove that it achieves a competitive ratio of max\2, min\γ, 3\\, where γ is the max/min storage cost ratio among all servers. Examples are given to confirm the tightness of competitive analysis. We also empirically evaluate algorithms using real object access traces.