Efficient Caching with Reserves via Marking¹¹1An extended abstract is to appear in the Proceedings of the 50th ICALP, 2023.

We study the Caching with Reserves model of Ibrahimpur et al. [10] in the online setting and improve upon those results. Our first main result is a simpler fractional algorithm that is a generalization of randomized marking for classical caching.

We remark that our algorithm in Theorem 1.1 and its analysis are more involved than those of the classical randomized marking algorithm. One complication is that due to the reserve constraints, a marking-style algorithm for the caching with reserves setting cannot evict an arbitrary unmarked page. Another key difficulty comes from the fact that even the notion of a phase is non-trivial to define in our setting. In particular, unlike in classical caching, it can happen that the cache still contains unmarked pages, but none of them can be evicted to make space for a new page, because of the reserve constraints. Thus, we need a rule to isolate agents whose reserve constraints prevent the algorithm from having a clean end of a phase, while also ensuring that the already marked pages of such isolated agents are not erased prematurely. To this end, we introduce the notion of global and local phases to effectively model the state of each agent. We elaborate on this in Section 3.1.

Our analysis of the fractional marking algorithm introduces two novel components that may be of independent interest. First, we upper-bound the total cost incurred by our fractional marking algorithm using a new potential function. This potential function, introduced in Section 3.3, depends only on the decisions of the algorithm and is independent of the optimal solution. To the best of our knowledge, all previous potential function based analyses of (variants of) caching [4, 5, 6, 10] define a potential function that depends on the optimal solution. Second, we introduce a new lower bound for the cost of the optimal solution via the dual-fitting method. Our techniques also yield a new simple proof that the classical randomized marking [9] for unweighted paging is $O(\log k)$-competitive (see Appendix A).

We also design a new online rounding algorithm that converts a deterministic, fractional algorithm into a randomized, integral algorithm while only incurring a constant factor loss in the competitive ratio. Via a careful discretization technique (inspired by Adamaszek et al. [2]), the new rounding algorithm runs in polynomial time and only uses limited randomization. Our fractional marking algorithm (Algorithm 1) maintains that at any point in time, a particular page $p$ is either completely in the cache or at least $1/k$ fraction of the page has been evicted. We exploit this key property to show that the fractional solution at any time $t$ can be discretized so that the fraction of any page that is evicted is an integral multiple of $1/k^{3}$. This discretization allows us to maintain a distribution over feasible integer cache states with bounded support.

The unweighted caching (also known as paging) problem has been widely studied and its optimal competitive ratio is well-understood even up to constant factors. Tight algorithms [1, 13] are known that yield a competitive ratio of exactly $H_{k}$, where $H_{k}$ is the $k$th harmonic number. Recently, Agrawal et al. [3] consider the parallel paging model where a common cache is shared among $p$ agents – each agent is presented with a request sequence of pages and the algorithm must decide how to partition the cache among agents at any time. It allows the $p$ processors to make progress simultaneously, i.e., incur cache hits and misses concurrently. Multi-agent paging has also been extensively studied in the systems community [7, 15, 16] often in the context of caching in multi-core systems. Closely related to the Caching with Reserves setting, motivated by fairness constraints in multi-agent settings, a number of recent systems  [11, 12, 14, 17] aim to provide isolation guarantees to each user, i.e., guarantee that the cache hit rate for each user is at least as much as what it would be if each user is allocated its own isolated cache. Also motivated by fairness constraints, Chiplunkar et al. [8] consider the Min-Max paging problem where the goal is to minimize the maximum number of page faults incurred by any agent.

The complete algorithm (referred to as Algorithm $\mathcal{A}$ in the proofs) is presented in Algorithm 1. We present a high-level discussion here. At any time $t$, we say that an agent $i$ is tight if $\sum_{p\in\mathcal{P}(i)}x_{p}^{t}=k_{i}$, i.e., the algorithm is not allowed to further evict any pages (even fractionally) of agent $i$. Conversely, an agent $i$ is non-tight if $\sum_{p\in\mathcal{P}(i)}x_{p}^{t}>k_{i}$.

The algorithm is a fractional marking algorithm and runs in phases where each phase corresponds to a maximal sequence of page requests that can be served while maintaining feasibility and ensuring that no “marked” pages are evicted. Within each phase, the currently requested page $p_{t}$ is fully fetched into cache by continuously evicting an infinitesimal amount of an “available” (described below) unmarked page $q$ with the smallest $y_{q}$ value; if there are multiple choices of $q$, then all of them are simultaneously evicted at the same rate. Page $p_{t}$ gets marked after it has been served and this mark may only be erased at the end of a phase.

At the end of a phase, an agent $i$ is designated as isolated if strictly fewer than $k_{i}$ $i$-pages are marked in the cache at this time point. This designation changes to non-isolated as soon as $k_{i}$ $i$-pages get marked at some point in the future. An isolated agent essentially runs a separate instance of caching on its own pages and in its own reserved space. At the end of a phase, the marks of pages owned by non-isolated agents (i.e., agents with at least $k_{i}$ marked $i$-pages) are erased.

It remains to describe when a page $q$ is considered available for eviction. Clearly, $y^{t}_{q}<1$ must hold, since otherwise page $q$ is already fully outside the cache. Moreover, $ag(q)$ must be non-tight, i.e., evicting page $q$ must not violate the reserve constraint of the agent that owns it. The last condition for $q$ to be considered available for eviction depends on whether the agent $i_{t}:=ag(p_{t})$ is isolated or not: (i) if agent $i_{t}$ is isolated, then $ag(q)=i_{t}$ should hold, i.e., only unmarked $i_{t}$-pages are available for eviction; and (ii) if agent $i_{t}$ is not isolated, then $ag(q)$ should also be non-isolated. We recall again that among all available pages for eviction, pages with the smallest $y^{t}_{q}$ value are evicted first.

At any time $t$, we consider the set of $y$ values of pages in $\bigcup_{i\in[m]}P(i,r_{i}-1)$ as the state of the system. We define a non-negative potential function $\Psi$ that is purely a function of this state. For any page request $p_{t}$, we attempt to bound the algorithm’s cost by an increase in the potential function, thereby bounding the total cost incurred by the algorithm by the final value of the potential function. There are two difficulties with this approach: (i) when a phase ends, the potential function abruptly drops since all the unmarked pages that were fully evicted no longer contribute to the state, and (ii) when the agent $i_{t}$ was isolated at the beginning of the phase but is now non-isolated, the change in potential is not sufficient to cover the fetch cost. In both these situations we charge the cost incurred by the online algorithm to a new quantity that is a function of the sets $\{P(i,r_{i})\}$. To complete the analysis, we show that this quantity is upper-bounded by the cost of the optimal solution.

Consider the function $\phi:[0,1]\to\mathbb{R}_{\geq 0}$ defined as:

As $h$ goes from $0$ to $1$, $\phi(h)$ increases from $0$ to $2\ln(1+k)$.

The potential at any time $t$ is defined as follows:

Note that only unmarked pages at any time $t$ contribute to the potential. So when page $p_{t}$ is fetched at time $t$ and marked, it stops contributing to the potential. But since $\phi$ is monotone, the newly evicted pages increase their contribution to the potential. We remark that the potential is purely a function of the state of the system as defined by the $y$ values of unmarked pages in the cache and is thus always bounded by a quantity independent of the length of the page request sequence.

The rest of this section is devoted to proving the following theorem where we bound the total cost incurred by the algorithm in terms of the sets $\{P(i,r_{i})\}$ and the number of requests to pseudo-clean pages.

Recall that the algorithm incurs a cost of $y_{p_{t}}^{t}$ to fetch page $p_{t}$ at time $t$. So the total cost incurred by the algorithm is simply $\mathrm{cost}_{\mathcal{A}}(\sigma)=\sum_{t}y_{p_{t}}^{t}$. We first bound this cost for time steps when the requested page $p_{t}$ is at least partially in the cache, i.e., $y_{p_{t}}^{t}<1$. Recall by Lemmas 3.2 and 3.4, the algorithm does not undergo a phase transition in this time step.

We still need to bound the cost incurred by the algorithm when the incoming request is to a page that is fully outside the cache. Note that the algorithm incurs exactly unit cost for all such time steps. The following lemma shows that the total cost incurred by the algorithm can be bounded by the drop in potential function at the end of a phase and by a term that depends only on the change in the potential function while processing a request to a page fully outside the cache.

So, it is enough to bound the total cost and drop in potential for time steps when the requested page is fully outside the cache and also to bound the drop in potential when the phase changes.

In this section, we give a novel LP-based lower bound on the cost of any offline algorithm for caching with reserves via dual-fitting. This lower bound analysis is new even for the classical unweighted paging setting. Crucially, the lower bound derived here perfectly matches the two terms used to bound the cost of the fractional algorithm $\mathcal{A}$ in Theorem 3.15, thereby completing the proof of our main result (Theorem 1.1).

We now describe the linear relaxation of the caching with reserves problem and its dual program. The following notation will be useful. For any page $q\in\mathcal{P}$, let $t_{q,1}<t_{q,2}<...$ denote the time steps when $q$ is requested in the online sequence. For an integer $a\geq 0$, define $I(q,a)=\{t_{q,a}+1,\ldots,t_{q,a+1}-1\}$ to be the time interval between the $a$th and $(a+1)$th requests for $q$. We define $t_{q,0}\triangleq 0$ for all pages. Let $a(q,t)$ denote the number of requests to page $q$ that have been seen until time $t$ (inclusive). Hence, by definition, for any time $t$ and page $q\in\mathcal{P}\setminus\{p_{t}\}$, we have $t\in I(q,a(q,t))$. The primal LP has variables $y(q,a)\in[0,1]$ which denote the portion of page $q$ that is evicted between its $a$th and $(a+1)$th requests, i.e., $1-y(q,a)$ portion of $q$ is held in the cache during the time-interval $I(q,a)$. For convenience, we define $n\triangleq|\mathcal{P}|$ and $n_{i}\triangleq|\mathcal{P}(i)|$ for any $i\in[m]$. The first and second set of primal constraints encode the cache size constraint and the agent-level reserve constraints for all times. The dual LP has variables $\alpha(t)$ and $\beta(t,i)$ corresponding to these primal constraints. We also have dual variables $\gamma(q,a)$ corresponding to the primal constraint encoding $y(q,a)\leq 1$. Besides nonnegativity, the dual has a single constraint for each interval $I(q,a)$. The primal and dual LPs are stated below. We emphasize that we use these linear programs purely for analysis and the algorithm itself does not need to solve any linear program.

Consider time $T$ that marks the end of a global phase $R_{0}$ for some integer $R_{0}$. Let $\mathrm{OPT}=\mathrm{cost}_{\mathrm{OPT}}(\sigma)$ denote the total cost incurred by an optimal offline algorithm. By weak LP duality, the objective function of the Dual LP yields a lower bound on $\mathrm{OPT}$ for any feasible dual solution. We now construct an explicit dual solution $(\alpha,\beta,\gamma)$ whose objective value is roughly equal to the total number of clean and pseudo-clean pages seen by the algorithm. See Section 3.1 to recall relevant notation and terminology. The dual solution is updated at the end of each (global) phase in two stages. Updates in the first stage, denoted $\mathsf{update}(r_{0},1)$, are simple and account for stale pages belonging to non-isolated agents that got evicted in the most recent local phase for that agent. Updates in the second stage, denoted $\mathsf{update}(r_{0},2)$, are more involved and account for the pseudo-clean pages of agents who lost their isolated status in the current phase. The dual solution that we maintain will always be approximately feasible up to $O(1)$ factors, so the objective value of this dual solution serves as a lower bound on $\mathrm{OPT}(T)$ within a constant factor. We remark that the assumption that $T$ marks the end of a phase is without loss of generality since it can lead to at most an additive $O(k)$ loss in the lower bound. Formally, we show the following.

We first show how Theorem 3.21 implies that our fractional algorithm $\mathcal{A}$ is $O(\log k)$-competitive.