2021-07-06
Efficient online weighted multi-level paging
Publication
Publication
We study the writeback-aware caching problem, a variant of classic paging where paging requests that modify data and requests that leave data intact are treated differently. We give an O(log^2 k) competitive randomized algorithm, answering an open question of Beckmann et al. [8] and Even et al. [21] about the existence of a randomized poly-logarithmic competitive algorithm. Our algorithm also works for arbitrary page weights. We also give an O(k) competitive deterministic algorithm, extending the previous result of Beckmann et al. [8] to the weighted setting. Interestingly, we also show that any polynomial-time randomized algorithm must be Ω(log^2 k)-competitive, assuming NP \not\subset BPP, based on a connection to online set-cover and using ideas of Feige and Korman [24]. This gives a surprising separation from the classical paging problem, where several tight O(log k)-competitive algorithms are known. A key underlying observation is that writeback-aware caching is algorithmically equivalent to Read/Write (RW) paging, which is an interesting problem on its own and has also been studied previously. We consider a further generalization of RW-paging to multi-level paging, where a page can have ℓ different types (RW-paging corresponds to ℓ=2), and give O(k)-competitive deterministic and O(log^2 k)-competitive polynomial-time randomized algorithms, without any dependence on ℓ. Our randomized algorithms are based on first finding an O(log k)-competitive fractional solution to an online linear problem that has additional complicating constraints beyond the usual covering or packing type. Then, we round this fractional solution online losing an additional O(log k) factor. For ℓ=1, which corresponds to the well-studied weighted paging, our approach gives a substantially simpler and natural rounding algorithm compared to the previous approaches, which might be of independent interest, albeit at the loss of an additional O(log k) factor.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1145/3409964.3461801 | |
| 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021 | |
| Organisation | Networks and Optimization |
|
Bansal, N., Naor, J., & Talmon, O. (2021). Efficient online weighted multi-level paging. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (pp. 94–104). doi:10.1145/3409964.3461801 |
|
