<p>In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of <span class="math-container">$1$</span>.</p>

<p>It is well known that for a <span class="math-container">$k$</span>-sized LRU cache has a competitive ratio of <span class="math-container">$k$</span> and that no deterministic algorithm can do better than that.</p>

<p>Consider the following (randomized) algorithm:</p>

<ol>
<li>We choose a random hash function that maps items into <span class="math-container">$\{1,\ldots,d\}$</span>.</li>
<li>Whenever we see a request, we hash it into one of <span class="math-container">$d$</span> LRU caches (of size <span class="math-container">$k/d$</span> each).</li>
</ol>

<blockquote>
  <p><strong>What is the competitive ratio of this limited associativity LRU variant?</strong> </p>
</blockquote>

<hr>

<p>It seems that if <span class="math-container">$k\gg d$</span>, we can use a balls-and-bins analysis to show that an input that consists of round robin of <span class="math-container">$k$</span> items will give a <span class="math-container">$k/d (1-o(1))$</span> lower bound.</p>

<ul>
<li>Is this tight?</li>
<li>What about other cases?</li>
</ul>

CC BY-SA 4.0
2019-01-14T23:46:28.200Z
No, it's not competitive as is.  Consider the case of k items that are requested repeatedly in round-robin fashion.  Clearly OPT has constant cost.  But with positive probability one of your d caches will receive more than k/d items, and so will fault repeatedly.  (I guess you need to use a slightly larger cache than OPT.  It seems difficult to ensure that your hash function partitions any set of k items into d groups of size k/d.)
Neal Young
CC BY-SA 4.0
2019-01-15T02:26:44.420Z
@NealYoung - good point.
R B
<ds.algorithms><approximation-algorithms><online-algorithms>
What is the competitive ratio of a $d$-way associative LRU cache?
R B
# What is the competitive ratio of a $d$-way associative LRU cache?

(Asked by: username_0 on 2019-01-14)

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.

It is well known that for a $k$-sized LRU cache has a competitive ratio of $k$ and that no deterministic algorithm can do better than that.

Consider the following (randomized) algorithm:

1. We choose a random hash function that maps items into $\{1,\ldots,d\}$.
2. Whenever we see a request, we hash it into one of $d$ LRU caches (of size $k/d$ each).

> **What is the competitive ratio of this limited associativity LRU variant?**

---

It seems that if $k\gg d$, we can use a balls-and-bins analysis to show that an input that consists of round robin of $k$ items will give a $k/d (1-o(1))$ lower bound.

* Is this tight?
* What about other cases?

**Tags:** ds.algorithms, approximation-algorithms, online-algorithms

> **Comments:**
> **username_1**: No, it's not competitive as is.  Consider the case of k items that are requested repeatedly in round-robin fashion.  Clearly OPT has constant cost.  But with positive probability one of your d caches will receive more than k/d items, and so will fault repeatedly.  (I guess you need to use a slightly larger cache than OPT.  It seems difficult to ensure that your hash function partitions any set of k items into d groups of size k/d.)  
> **username_0**: @NealYoung - good point.  

---

## 0 answers

