What is the competitive ratio of a $d$-way associative LRU cache?

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?
• 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 Jan 14 at 23:46
• @NealYoung - good point. – R B Jan 15 at 2:26