Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.24098 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911236487118848 |
|---|---|
| author | Zuo, Tianyu Tang, Xueyan Lee, Bu Sung Cai, Jianfei |
| author_facet | Zuo, Tianyu Tang, Xueyan Lee, Bu Sung Cai, Jianfei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24098 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Competitiveness of Dynamic Replication for Distributed Data Access Zuo, Tianyu Tang, Xueyan Lee, Bu Sung Cai, Jianfei Data Structures and Algorithms 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. |
| title | On Competitiveness of Dynamic Replication for Distributed Data Access |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.24098 |