Roee Engelberg on triangulation and embedding using small sets of beacons

Theory Lunch, October 5, 2005

Minutes by Kunal Talwar

Paging problem: 

Try to minimize number of page faults.

Goal: Design algorithms with a good competitive ratio.

Competitive ratio of the online algorithm is defined as maxs { costA(s) / costOPT(s).

Known: Deterministic case: FIFO, LRU etc. are k-competitive. Lower bound of k.

Now suppose that this computer is a database server, say AA. Still the same cache, but now each request is designated to a user. Users try to minimize the number of their own page faults. Now when there is a page fault, the user causing the page fault decides which page to evict. We can expect selfish behavior by users. Use game-theoretic approach to study the problem.

Paging game :

This is a symmetric game. We'll look at symmetric equilibria.

Let's look at some strategies.

LRU (Least Recently Used): Many ways to define it.

  1. LRUs Evict page least recently used by yourself. This is bad. Example:

    LRUs: . . . 1 . 1 2; 3 2; 1 2; 3 2; . . .
    OPT: . . .; 1 .; 1 2; 1 3;. . ..

    LRUs has an unbounded number of page faults. OPT is constant.

  2.  Another option: "Global" LRU.

    Claim: This is an equilibrium. To show this, it suffices to show that global LRU has competitive ratio k for a particular agent. This is enough because you cannot do better than k even if what just you.

    Gives a competitive ratio of $k$

    Divide into phases. Phase rho ends before the later of the following two events:
    1. (k+1) different pages in \rho.
    2. OPT's first page fault (excluding 1st request)

    In each phase, OPT has at least one page fault.

    In first case: LRU has at most k.

    In second case: when the page fault occurs in OPT, LRU has same set of pages as OPT. If OPT has no more page faults, LRU doesn't either.

Now let's look at FIFO

FIFOs is bad for the same example as LRUs
"global" FIFO is also bad. Somewhat complicated example, see paper.
Thus LRU is stable, FIFO is not.

In practice, we know LRU is better than FIFO, but not in the competitive ratio sense. This is one way in which it's better.


EXAMPLES:

Caching in P2P systems

Network Design Problem

Routing

Q: What if you could evict a page only if its placed by one of your requests?

A: Not immediately well defined. None of your pages could be in there.

Q: Randomized algorithms are better for the caching game. What happens here?

A: Not clear. Dependencies between player's actions.

Q: Are the good solutions always of a global nature?

A: Not always the case, in n/w design e.g. it may be better to use selfish strategies.

(Kunal's aside: Even in the non game theoretic sense, this argument shows that LRU is better than FIFO in the following way: suppose that we care about a subsequence and just look at the competitive ratio for the subsequence. This argument says that FIFO is not competitive in this sense while LRU is!)