تقرير
Cost-Driven Data Replication with Predictions
| العنوان: | Cost-Driven Data Replication with Predictions |
|---|---|
| المؤلفون: | Zuo, Tianyu, Tang, Xueyan, Lee, Bu Sung |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | This paper studies an online replication problem for distributed data access. The goal is to dynamically create and delete data copies in a multi-server system as time passes to minimize the total storage and network cost of serving access requests. We study the problem in the emergent learning-augmented setting, assuming simple binary predictions about inter-request times at individual servers. We develop an online algorithm and prove that it is ($\frac{5+\alpha}{3}$)-consistent (competitiveness under perfect predictions) and ($1 + \frac{1}{\alpha}$)-robust (competitiveness under terrible predictions), where $\alpha \in (0, 1]$ is a hyper-parameter representing the level of distrust in the predictions. We also study the impact of mispredictions on the competitive ratio of the proposed algorithm and adapt it to achieve a bounded robustness while retaining its consistency. We further establish a lower bound of $\frac{3}{2}$ on the consistency of any deterministic learning-augmented algorithm. Experimental evaluations are carried out to evaluate our algorithms using real data access traces. Comment: The formal version of this draft will appear in ACM SPAA'24 conference |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1145/3626183.3659964 |
| الوصول الحر: | http://arxiv.org/abs/2404.16489Test |
| رقم الانضمام: | edsarx.2404.16489 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1145/3626183.3659964 |
|---|