Contents lruis2: LRU is k-competitive for the paging problem Jan 29 05:27 lfd: An optimal offline algorithm for the paging problem Jan 29 06:12 2002 lowerdet: Lower bound of k on the deterministic competitiveness Jan 24 04:17 2002 workf01: Work functions for the paging problem I Jan 30 03:21 2002 workf02: Work functions for the paging problem II Jan 31 09:32 2002 bookmarks: Bookmark algorithms for the paging problem I Feb 2 10:29 2002 bookmark1: Bookmark algorithms for the paging problem II Feb 11 15:11 2002 The lowest competitiveness for any randomized algorithm for the paging problem is known to be H_k. The lowest competitiveness for any known randomized algorithm for the paging problem that uses no bookmarks is 2H_k - 1. It is natural to ask whether there a tradeoff between the number of bookmarks and competitiveness. Theorem 1. EQUITABLE is an H_k compeititive randomized algorithm that uses O(k^2 log k) bookmarks. The actual formula is approximately (5 k^2 H_k), which works out to abut 30 if k = 2. Theorem 2. There is no 3/2 competitive randomized algorithm for the paging problem for k = 2 that uses no bookmarks. Theorem 3. There is a 3/2 competitive randomized algorithm for the paging problem for k = 2 that uses at most one bookmark at any given time. Problem. What is the minimum number of bookmarks needed for the case k = 3, to achieve 11/6 competitiveness? The number certainly does not exceed the number needed by EQUITABLE, but that number is ridiculously large. Open Problem. For general k, find a relationship between the number of bookmarks used and the competitiveness. More specifically, Borodin and El Yaniv as whether we can obtain H_k competitiveness with O(k) bookmarks. We define the k^th "harmonic number" H_k to be the sum of the reciprocals of the first k positive numbers. For example, H_1 = 1, H_2 = 3/2, H_3 = 11/6, and H_4 = 25/12. Note that H_k = Theta(log k); in fact, H_k is very close to log_2(k). There is a randomized algorithm for the paging problem which is H_k competitive for cache size k. That algorithm, PARTITION, is rather complicated. Here, we give a highly simplified version, which we call Bookmarks, which works only for k = 2. At any given time, the algorithm maintains a list of "bookmarked" pages in slow memory. There is no limit to the length of this list. Initially, there are no bookmarks. We call the two pages in cache the "lru" page and the "mru" page. The mru page is defined to be the page that was requested in the previous step, while the lru page is simply the other one. Each time a request is made, those labels may change. Bookmarks: 1. If mru is requested, do nothing. 2. If lru is requested, erase all bookmarks. 3. If a bookmarked page is requested, eject lru and erase all bookmarks. 4. If there are M bookmarks, and then an unbookmarked page in slow memory is requested, eject lru with probability 1/(M+2), and eject mru with probability (M+1)/(M+2). Bookmark the ejected page. (There will now be M+1 bookmarks.) Theorem: Bookmarks is 3/2-competitive. Proof: Define a "phase" as follows. Before the first request of a phase, the support of the work function consists of one configuration. The last request of a phase is when the support of the work function is once again just one configuration, except for a possibly incomplete phase at the end. The proof consists of first verifying the following claims. We omit these verifications. Claim 1: The cardinality of Supp(w) is M+1, where M is the number of bookmarks. If b_1, ... b_M are the bookmarked pages, Supp(w) consists of the pairs (mru,lru), (mru,b_1), ... (mru,b_M). Claim 2: If X in Supp(w), the probability that (mru,lru) = X is 1/(M+1). Claim 3: If the length of a complete phase is d, then the optimal cost for that phase is at least d-1. For an imcomplete phase of length d, the optimal cost is d. Claim 4: If the length of a phase is d, then Bookmark's cost for that phase is d - 1/d. For an incomplete phase of length d, the Bookmark's cost is d. The Theorem follows immediately from the claims. The Longest Forward Distance algorithm (LFD) for the paging problem. LFD is defined as follows. Let x be the current request. 1. If x is in the cache, do nothing. 2. If x is not in the cache, copy x into the cache, and eject that page whose next request is farthest in the future. In case two or more cache pages are never requested in the future, eject one of those arbitrarily. Theorem 1: LFD is optimal. I will not give a proof here. Local Optimality. We can say that an offline algorithm A is "locally optimal" if, after any number of steps, A is optimal for the sequence of requests so far. Local Optimality Hypothesis (LOH): There exists a locally optimal offline algorithm. Theorem 2: LFD is locally optimal for the paging problem. That is to say, if rho = r_1 r_2 .... r_N, then LFD, looking at the entire sequence, is still optimal for the truncated sequence r_1 ... r_M for any M. Problem: Does LOH hold for every online problem? Example. Suppose k = 2, and the request sequence is (ab)cabdefbac. My notation indicates that the initial cache is (ab) and that the actual request sequence is cabdefb. After step 1, the LFD cache is (ca). After step 2, the LFD cache is (ab). After step 3, the LFD cache is (ba). (I use the rule that the mru is first) After step 4, the LFD cache is (db). After step 5, the LFD cache is (eb). After step 6, the LFD cache is (fb). After step 7, the LFD cache is (bf). After step 8, the LFD cache is (ab) or (af). (There is an arbitrary choice.) After step 9, the LFD cache is (ca), (cb), or (cf). (Do you see why?) The total cost of LFD is 7, which is optimal for this sequence. But what about the situation after 6 steps? At that time, LFD has paid 5. Could some other offline algorithm service the first 6 steps at smaller cost? The answer is no: 5 is the optimal cost for the request sequence (ab)cabdef. Now look at it from the point of view of an online observer, i.e., someone who only knows the past requests, but realizes that there might be future requests. After one step, the online observer knows that LFD's cache is either (ca) or (cb), but cannot determine which. But after 2 steps, the online observer knows that LFD's cache is (ac). After 6 steps, the online observer knows that LFD's cache must be (fa), (fb), (fc), (fd), or (fe). After 7 steps, the online observer, once again, knows LFD's cache for sure. Problem: Show that there exists an optimal offline algorithm for the paging problem for k = 2 which does not satisfy LOH. Hint: look at the request sequence (ab)cba. Theorem 2. There is no online deterministic algorithm for the cache problem of competitiveness less than k, where k is the cache size. Suppose that A is a deterministic online algorithm for the cache problem. We will design a request sequence such that A pays at least k times the cost of the optimal offline algorithm. This request sequence will utilize only k+1 distinct pages. Let P be a set of k+1 pages, such that the initial cache is a subset of P. At each step, let the request be to the one member of P which is not in A's cache. Thus, A faults at every step. Call this request sequence rho. (rho is called the "cruel" request sequence.) We partition rho into "phases" as follows. The first phase begins with the first request. Phases are as long as possible, subject to the rule that no phase contains all members of P. If a phase cannot be continued, a new phase begins. (For example, suppose k = 4, and rho = ebecbdeabcedaebecdabecdadabeb. Then the partitioning of rho into phases is: ebecbde|abce|daebe|cdab|ecdada|beb.) Claim 1: Each phase (except perhaps for the last one) has length at least k. Proof: A new phase cannot begin until k distinct pages have been requested on the old phase. Claim 2: Opt faults at most once during each phase. Proof: At the beginning of each phase, Opt ejects a page that will not be requested during that phase. (There is always just one such page, except possibly for the last phase.) Opt will then have no further faults during that phase. We now finish the proof of Theorem 2. Let N be the length of rho, and let M be the number of phases. Then A pays N. By Claim 2, Opt pays at most M. By Claim 1, N >= (M-1)k+1. The ratio N/M is thus bounded below by k, as N grows without bound. LRU is k-competitive for the paging problem. Let k be the size of the cache. Theorem 1: LRU is k-competitive. Proof: Let Opt be the optimal offline algorithm. (N.B.: we do not have to assume that Opt is LFD.) We assume that the initial cache is given. (This is a standard assumption of the problem.) Let rho be the request sequence. Partition rho into "phases." The definition of a phase is that Opt faults on the first request of each phase, but does not fault on any other request of that phase. Thus, the total cost of Opt is the number of phases. Claim 1: For any given phase, let K be the set of pages in Opt's cache after the first request of that phase. Then all requests of that phase are to members of K. Proof of Claim: Any request outside K would cause Opt to fault, contradicting the assumption that Opt does not fault after the first request of the phase. Claim 2: If a page p is requested during a phase, LRU will not eject p during the remainder of that phase. Proof: suppose that page q is the i^th request of the phase, and that Q is the set of all pages requested in the first i requests of the phase. Since the cardinality of Q is at most k, and since each member of Q has been requested more recently than any page not in Q, LRU will not eject any member of Q when q is requested. Claim 3: For any given phase, let K be the set described above. Then, after LRU has faulted i times during that phase, LRU's cache contains at least i members of K. Proof: After i faults, LRU has brought i members of K into its cache. By Claim 2, none of these have been later ejected, so they are still there after i requests. Claim 4: LRU faults at most k times during any phase. Proof: Since K has only k members, Claim 3 shows that LRU cannot fault more than k times during the phase. We now complete the proof of Theorem 1. Let N be the number of phases. By definition, Opt pays N. By Claim 4, LRU pays at most Nk. 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. Work Functions. We say that a work function w is a "cone" if Supp(w) consists of a single configuration. We define an operator called "update." If w is a work function and r is a request, then (w update r) is a work function. The meaning of the update operator is that, if w is the work function before a request r, then (w update r) is the work function after that request. Thus, if r^t is the request at step t, and if w^t is the work function after step t, then w^t = (w^{t-1} update r^t). What is the domain of a work function? This is controversial, as there are two sensible answers. Define Config_t to be the set of all configurations that are possible after step t, according to the rules of the problem. For example, in the paging problem, Config_t is all possible cache configurations which contain the page r_t. It would make sense to say that the domain of the work function w^t is Config_t, but an alternative is to define the domain of w^t to be Config, the set of all configurations. In the paging problem, Config is the set of all distinct unordered k-tuples of pages. {Footnote: unordered, because from the standpoint of work functions, all cache locations are equivalent, and it does not matter how long a given page has been in the cache. This is true despite the fact that some online algorithms, such as LRU, keep an ordering of the cache pages based on how long they've been in the cache.} The way to think of it is that we change change the rules so that, after reading or writing the requested page, an algorithm can eject any number of pages (including the one just requested) and replace them with arbitrary other pages, at a cost of 1 each, of course. We call this a "non-lazy move," and an algorithm that never makes such a move we call "lazy." Common sense tells us that an algorithm can do just as well or better by never making non-lazy moves, but an offline algorithm could do it without harm by using its knowledge of the future. By allowing non-lazy moves, any configuration can be achieved after each step, thus allowing the domain of the work function to be all of Config. Theoretically, these two approaches are equivalent, so the choice should be made on practical grounds. For purposes of computer programs, restricting the domain is usually the best choice, because it decreases the size of the data structures needed. But for purposes of writing definitions and proofs, allowing the domain to be Config is simpler, so that is the choice we make. {Footnote: if you were writing a program, even Config_t might be very large, so you would like the domain of w^t to be even more restricted. How small could you make it?} Let X^0 be the initial configuration, i.e., the initial cache. Define w^0 as follows: for any configuration Y, w^0(Y) = |X^0,Y|. Thus, Supp(w^0) = {X^0}. If w is any work function and if r is any request, let Config_r be the set of all possible cache configurations that contain r. We then define the work function (w update r) as follows: For any configuration Y, (w update r)(Y) = min_{X in Config_r}(w(X) + |X,Y|). Finally, for any step t, define w^t = (w^{t-1} update r^t), where r^t is the request at step t. Note that we abuse notation by writing Config_r^t and Config_t to mean the same thing. Exercise we'll work Monday in class: Consider the request sequence (abc)daeac for the paging problem for k=3. Compute Supp(w^t) for t = 0,1,2,3,4,5. Try to work it out in advance so that you can help me.