  Caching is a crucial component of many computer systems, so naturally it is a
well-studied topic in algorithm design. Much of traditional caching research
studies cache management for a single-user or single-processor environment. In
this paper, we propose two related generalizations of the classical caching
problem that capture issues that arise in a multi-user or multi-processor
environment. In the caching with reserves problem, a caching algorithm is
required to maintain at least $k_i$ pages belonging to user $i$ in the cache at
any time, for some given reserve capacities $k_i$. In the public-private
caching problem, the cache of total size $k$ is partitioned into subcaches, a
private cache of size $k_i$ for each user $i$ and a shared public cache usable
by any user. In both of these models, as in the classical caching framework,
the objective of the algorithm is to dynamically maintain the cache so as to
minimize the total number of cache misses.
  We show that caching with reserves and public-private caching models are
equivalent up to constant factors, and thus focus on the former. Unlike
classical caching, both of these models turn out to be NP-hard even in the
offline setting, where the page sequence is known in advance. For the offline
setting, we design a 2-approximation algorithm, whose analysis carefully keeps
track of a potential function to bound the cost. In the online setting, we
first design an $O(\ln k)$-competitive fractional algorithm using the
primal-dual framework, and then show how to convert it online to a randomized
integral algorithm with the same guarantee.
