Randomized method improves page caching with time delays and weights
Tight weighted paging with delay via mirror descent
Data Structures and Algorithms
Summary
The problem is deciding when to fetch and replace pages (pieces of data) in a limited memory efficiently, even when requests can wait for some time with a cost penalty. The authors improve on past methods by creating an algorithm that is both fair and efficient, achieving the best possible performance relative to the number of pages held in memory, independent of the total number of pages. They combine advanced mathematical tools with strategies to handle delays in serving requests. Their solution is randomized and can be applied in systems that use caching with delayed responses.
What this means in practice
- •For operating system developers: Optimize memory caching strategies in operating systems to handle weighted page requests with delay penalties more efficiently.
- •For cloud infrastructure engineers: Improve cache management in cloud servers to reduce costs associated with delayed data requests and weighted resource access.
Authors
Julian Born, Yann Disser, Linda Thelen
Abstract
We give an O(log k)-competitive randomized algorithm for weighted paging with delay. This improves upon the O(log k log n)-competitive algorithm of Gupta, Kumar, and Panigrahi (STOC 2020, SICOMP 2022) by removing the dependence on the number n of pages. Without delay, the optimal competitive ratio of randomized algorithms is Theta(log k), and since the lower bound carries over, our bound is tight. Our algorithm is fractional and combines mirror descent, used by Bubeck et al. (STOC 2018) for weighted paging without delay, with preemptive service, introduced by Azar et al. (STOC 2017) for online service with delay: when a request is served, an increase in the mirror descent potential is offset by preemptive service to other pending requests, with a budget derived from the mirror descent path. To obtain a randomized algorithm, we use the online rounding of Bansal, Buchbinder, and Naor (FOCS 2007) from classical paging.