Caching with Dual Costs
Anirban Dasgupta, Ravi Kumar, Tamás Sarlós · 2017
Caching mechanisms in distributed and social settings face the issue that the items can frequently change, requiring the cached versions to be updated to maintain coherence. There is thus a trade-off between incurring cache misses on read requests and cache hits on update requests. Motivated by this we consider the following dual cost variant of the classical caching problem: each request for an item can be either a read or a write. If the request is read and the item is not in the cache, then a read-miss cost is incurred and if the request is write and the item is in the cache, then a write-hit cost is incurred. The goal is to design a caching algorithm that minimizes the sum of read-miss and write-hit costs. We study online and offline algorithms for this problem.