Efficient Caching with Reserves via Marking

Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua R. Wang

Abstract

This paper introduces a simplified framework for analyzing online caching problems using a combination of state-only potential functions and dual-fitting. We apply this framework to the "Caching with Reserves" model—a fair-sharing variant of the classic paging problem designed for multi-user environments. We achieve an $O(\log k)$-competitive ratio for both fractional and randomized integral algorithms. Notably, our randomized integral algorithm is the first to achieve this ratio while running in polynomial time, overcoming the exponential complexity of previous rounding schemes.

Introduction

In the classical paging problem, a system manages a cache of size $k$. When a requested page is not present (a "miss"), the system must evict an existing page to accommodate the new one. The objective is to minimize the total number of misses. While the paging problem is well-understood in single-user contexts, it presents challenges in multi-user environments like cloud computing. In these scenarios, a single "heavy" user can monopolize the cache, evicting other users' data and leading to significant performance degradation and unfairness.

To address this, the Caching with Reserves model (Ibrahimpur et al., 2022) guarantees each user $i$ a minimum "reserve" of $k_i$ pages in the cache at all times. While this modification ensures fairness, it significantly increases the problem's complexity; even the offline version, where all future requests are known, is NP-hard. Previous online solutions were either too complex for practical implementation or required exponential time to convert fractional strategies into concrete page evictions.

The Fractional Marking Algorithm

We propose a Fractional Marking Algorithm that generalizes the classic "Randomized Marking" approach to accommodate reserve constraints. The algorithm operates through a series of phases:

  1. Marking Mechanism: Pages are "marked" upon request. A phase concludes when the cache is entirely filled with marked pages.
  2. Reserve Constraints and Isolated Agents: Unlike standard paging, the algorithm may encounter "unmarked" pages that it cannot evict because doing so would violate a user's reserve. To manage this, we introduce the concept of "isolated agents." These are users who have not yet reached their reserve capacity. These agents effectively run local caching instances until they meet their reserve, at which point they reintegrate into the global marking process.
  3. Discretization and Rounding: A key contribution of this work is a new discretization scheme that converts fractional "probabilities" of page residency into a concrete randomized schedule. This rounding process is achieved in polynomial time, making the algorithm computationally feasible.

Theoretical Framework: Potential Functions and Dual-Fitting

The core theoretical innovation of this paper is a simplified analysis framework that avoids the complexities of traditional "coupling" arguments.

State-Only Potential Functions

Traditionally, potential functions in caching measure the "distance" between the state of the online algorithm and the optimal offline solution (OPT). This requires tracking the state of an unknown optimal adversary. In contrast, our potential function $\Phi$ depends solely on the algorithm's own eviction state. Specifically, we utilize a function of the form $\phi(h) = 2h \ln(1 + kh)$, where $h$ represents the algorithm's current state. This shift significantly simplifies the logic required to bound the algorithm's costs.

Dual-Fitting Synergy

We complement the potential function analysis with dual-fitting. By formulating the caching problem as a Linear Program (LP), we use the Dual LP to establish a lower bound for the optimal offline cost. We demonstrate that the costs incurred by our algorithm are directly proportional to the growth of this dual objective. This synergy provides a robust "certificate" of performance, showing that the algorithm's competitive ratio is maintained relative to any possible offline strategy.

Key Results

Our analysis yields several significant results for the Caching with Reserves model:

  • Competitive Ratio: The fractional marking algorithm is proven to be $O(\log k)$-competitive. This ensures that even in the worst-case request sequence, the algorithm's performance is within a logarithmic factor of the theoretical optimum.
  • Polynomial-Time Implementation: We provide the first $O(\log k)$-competitive randomized integral algorithm for this model that runs in polynomial time.
  • Simplification of Classical Paging: As a secondary benefit, our state-only potential function technique provides a more elegant and concise proof for the $O(\log k)$ competitiveness of the standard randomized marking algorithm in the original, unweighted paging problem.

Conclusion and Future Work

While this framework successfully addresses the Caching with Reserves model, several avenues for future research remain. The current marking-based approach is optimized for uniform fetch costs; extending these techniques to Weighted Caching, where different pages have different eviction costs, may require further adaptation of the potential function. Additionally, we are interested in whether these dual-fitting techniques can be applied to the k-server problem, a more general abstraction of caching where points move within a metric space. Finally, future work may focus on tightening the constant factors within the $O(\log k)$ guarantee to further improve practical performance bounds.

Summary updated

BibTeX
@inproceedings{ibrahimpur2023efficient,
  author = {Sharat Ibrahimpur and Manish Purohit and Zoya Svitkina and Erik Vee and Joshua R. Wang},
  title = {{Efficient Caching with Reserves via Marking}},
  booktitle = {ICALP},
  year = {2023},
  doi = {10.4230/lipics.icalp.2023.80},
}
Figure