The ubiquity of caches has motivated extensive research on the performance of existing caching policies, as well as on the design of new policies with provable guarantees. To that end, most prior work has assumed that caches serve requests generated according to a stochastic process, ranging from the simple, memory-less independent reference model [1]} to more complex models trying to capture temporal locality effects and time-varying popularities (e.g., the shot-noise model [2]}).
An alternative modeling approach is to consider an adversarial setting. Assuming that the sequence of requests is generated by an adversary, an online caching policy can be compared to the optimal offline policy that views the sequence of requests in advance.
Caching was indeed one of the first problems studied by Sleator and Tarjan in the context of the competitive analysis of online algorithms [3]}. In competitive analysis, the metric of interest is the competitive ratio, i.e., the worst-case ratio between the costs incurred by the online algorithm and the optimal offline dynamic algorithm.
This line of work led to the study of metrical task systems [4]}, a popular research area in the algorithms community [5]}.
