{"ID":2848932,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.24098","arxiv_id":"2510.24098","title":"On Competitiveness of Dynamic Replication for Distributed Data Access","abstract":"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.","short_abstract":"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 an...","url_abs":"https://arxiv.org/abs/2510.24098","url_pdf":"https://arxiv.org/pdf/2510.24098v1","authors":"[\"Tianyu Zuo\",\"Xueyan Tang\",\"Bu Sung Lee\",\"Jianfei Cai\"]","published":"2025-10-28T06:10:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}