On Variants of File Caching

for files out of a slow memory. A file has two attributes, a
retrieval cost and an integer size. It is required to maintain a
cache of size k, bringing each file, which is not present in
the cache at the time of request, from the slow memory into the
cache. This incurs a cost equal to the retrieval cost of the file.
Well-known special cases include paging (all costs and sizes are
equal to 1), the cost model which is also known as weighted paging
(all sizes are equal to 1), the fault model (all costs are equal to
1)
and the bit model (the cost of a file is equal to its size).

We study two online variants of the problem, "caching with
bypassing" and "caching with rejection". If bypassing is
allowed, a miss for a file still results in an access to this file
in the slow memory, but its subsequent insertion into the cache is
optional. In the model with rejection, together with each request
for a file, the algorithm is informed with a rejection penalty of
the request. When a file which is not present in the cache is
requested, the algorithm must either bring the file into the
cache, paying the retrieval cost of the file, or reject the file,
paying the rejection penalty of the request. The goal function is
the sum of total rejection penalty and the total retrieval cost.

We design deterministic and randomized algorithms for both problems.
The competitive ratios of these randomized algorithms match the best
known results for caching. In the deterministic case, it is known
that a (k+1)-competitive algorithm for caching with bypassing exists,
and this is best possible. In contrast, we present a lower bound of
2k+1 on the competitive ratio of any deterministic algorithm for the
variant with rejection, which holds already for paging. We design a
(2k+2)-competitive algorithm for caching with rejection, and a
different (2k+1)-competitive algorithm , which is applicable for
paging, the bit model and the cost model.

joint work with Csanád Imreh, Asaf Levin, and Judit Nagy-György