ok, so you might have heard of paging, which is basically where you havea cache of pages, and you repeatedly get new page, and you have to deicde which pages to evict whenever you get a page that is not in your cache.
Today we’re going to talk about a generalization of paging, called \(k\)-server. In \(k\)-server you now live in a metric space and your score is the total distance your servers travel.
The way I like to think of it is you have a bunch of ice-cream trucks in a city. Over time you get some requests for ice cream. The trucks are really fast, but gas is really expensive. So you want to minimize the total distance that your ice-cream trucks travel to meet all the requests.
Paging is this problem under the discrete metric (i.e. all non-identical points are distance \(1\) from each other).
ok, but what can we say about non-discrete metrics?
Actually we are only going to consider a very special case today: online on-a-line \(k\)-server. That is, we consider the metric space of a line.
Claim. There are at most \(2\) servers that are reasonable to move: the closest server to the right/left of the request.
Proof. Imagine you thought it was a good idea to move someone else. Now when he moves past one of the dudes you were really supposed to move they swap hats and the dude you really should have moved goes in place of the other dude, but you are none the wiser.
ok, now we have \(2\) options for what to move instead of having to consider all \(k\) servers that we could move. But how to choose? The “correct choice” depends on the future sequence of requests. It certainly seems tricky. So we just don’t choose! Double Coverage Algorithm: move both closest servers closer to the target until one hits it.
Theorem. Double coverage is \(k\) competitive.
We use the following potential function: \[\phi = k\cdot M + \sum_{ij}d(s_i,s_j)\] where \(M\) denotes the min-cost matching between our servers \(s_i\) and OPT’s servers \(o_i\).
Imagine stuff happening with OPT moving first and then us moving for each request.
Claim. Whenever opt moves by \(d\) potential increases by at most \(kd\).
Proof. This is immediate.
Lemma. Whenever double coverage moves by \(d\) potential decreases by at least \(d\).
Proof. If the request is to the right/left of all servers: matching cost decreases by \(d\) because we are moving on to the opt server, and the \(\sum d(s_i,s_j)\) thing increases by \((k-1)d\). Overall potential decreases by \(d\).
If the request is in the middle of stuff then matching cost doesn’t increase, and most of the \(\sum d(s_i,s_j)\) changes cancel, just the two dudes that we are moving get closer, by \(2d\).
Theorem. Double coverage is \(k\)-competitive.
Proof. opt total dist \(-\) our total dist \(*1/k\) is \(\phi\). But \(\phi\) never goes crazy or anything so this is fine.
