Work Functions Work functions can be defined for many online problems, including the paging problem. A work function is a snapshot, in time, of the dynamic programming calculation of the optimal cost of servicing the request sequence. The work function is known to the online observer. We give an example, using the paging problem for k = 2. Consider the request sequence (ab)cabdc. That means, the initial cache is (ab) and there are five requests: c,a,b,d,c. The domain of the work function is the set of all possible configurations, where that is, in this case, defined to be the set of all possible pairs of pages that could be in the cache. It is not necessary in this computation to distinguish the lru page from the mru page. Thus, for this instance, there are 6 pairs. Let w^t be the work function after t steps. The initial work function w^0 is defined as follows: w^0(ab) = 0 w^0(xy) = the minimum cost of changing the cache (ab) to the cache (xy). That is, we allow an algorithm to eject any page at any time and replace it by any page, regardless of the request. You might ask, why would an algorithm bring in a page that is not requested? The answer is that, in practice, it would not, but it is useful to consider this option while computing work functions. For any t, and for any two pages x and y, w^t(xy) is defined to be the minimum cost of servicing the first t requests and ending with xy in the cache. The following table gives w^t for all t from 0 to 5 in our example (ab)cabdc: ab ac ad bc bd cd w^0 0 1 1 1 1 2 w^1 2 1 2 1 2 2 w^2 2 1 2 2 3 2 w^3 2 3 3 2 3 3 w^4 4 4 3 4 3 3 w^5 5 4 4 4 4 3 Lipschitz condition. If X and Y are configurations, and if w is a work function, and if |X,Y| is the cost of changing configuration X to configuration Y, then w(Y) <= w(X) + |X,Y|. This is called the Lipschitz condition. For example, in the above table, w^1(ac) = 1 and |ac,ab| = 1, since the cost of changing from having ac in the cache to having ab in the cache is 1. Thus, we can know that w^1(ab) <= 2. Support. Each work function w is "supported" by a subset of the configurations, which we call Supp(w). If X is not in Supp(w), then w(X) is the maximum allowed by the Lipschitz condition. Thus, in our example, Supp(w^0) = {(ab)}, Supp(w^1) = {(ac),(bc)}, and Supp(w^2) = {(ac)}. Exercise: Compute Supp(w^t) for t = 3,4,5. Problem: Prove that, for any proof of competitiveness, the optimal cache is in Supp(w) without loss of generality. I want you to prove this for the paging problem for k = 2, but in fact, it is true in general.