6.854 Advanced AlgorithmsLecture 20: 11/01/2004 Lecturer: David KargerScribes: Tushara C. KarunaratnaOnline Algorithms (continued)20.1 IntroductionIn the previous lecture, we defined the term competitive ratio for deterministic online algorithms.We studied a 2-competitive algorithm for ski-rental. We also observed that our greedy algorithm forload balancing is a 2-competitive online algorithm.In this lecture, we will study online algorithms for paging, finance, and k-server on a line.20.2 PagingPaging is an important problem in computer systems design. We model a machine’s memory asconsisting of two parts: an unlimited number of pages of slow memory, and a cache consisting of kpages of fast memory. On a page request, if the requested page is not in the cache (we call this acache miss or a fault), then a page in the cache must be evicted and the requested page must bebrought in. A paging strategy specifies the choice of which page to evict on a cache miss. The goalis to minimize the number of cache misse s.Here are the some of the commonly used paging strategies.• LRU: evict the leas t recently used page. We will prove that this strategy is k-competitive.• Random: evict a random page. It is known that this strategy is k-competitive.• FIFO: evict the earliest fetched page. It is known that this strategy is k-competitive.• Frequency counts: evict the least frequently used page. It is known that this strategy is notcompetitive.20.2.1 LRU is k-competitiveTo analyse the performance of LRU, we partition the input sequence into phases. The first phasebegins immediately after LRU first faults. A phase ends immediately after LRU has faulted k timessince the start of the phase; the next phase begins at this point.20-1Lecture 20: 11/01/2004 20-2We now prove that OPT faults at least once per phase.Consider any phase such that LRU faults twice on some page p in this phase. We know that at leastk other distinct pages must have been requested in between the two requests of p (because otherwisep would not have been evicted by LRU). Hence, there are at least k + 1 distinct pages requested inthis phase, and thus OPT faults at least once in this phase.On the other hand, consider any phase such that LRU faults on k distinct pages in this phase. Le tp be the last fault of the previous phase. Note that even if p is one of the k faults in this phase, atleast k other distinct pages must have been requested in this phase (because otherwise p would nothave been evicted by LRU). Since p was in OPT’s cache at the start of this phase, OPT faults atleast once in this phase.Therefore, LRU is k-competitive.20.2.2 Lower bound for deterministic online pagingConsider any deterministic online paging algorithm A.We construct a request sequence involving k + 1 pages; at each step, we request the page that is notin A’s cache. Note that for this s equence, A faults on every request.Consider the offline algorithm that, on a cache miss, evicts the page that is requested furthest inthe future. When this offline algorithm faults, the page that it evicted won’t be requested until atleast k steps in the future. Therefore, this offline algorithm faults only once every k requests for ourabove adverserial sequence.Therefore, no deterministic online paging algorithm can be better than k-compe titive.20.3 FinanceWe own some amount of stock. We have no information on how the price per unit of the stock mayfluctate in the future, but we know that the peak price is M and that the minimum price is m. Wewant to sell our stock so as to maximize our return.20.3.1 Reserve price algorithmThe stategy is to sell all our stock the first time that the price beats r.We claim that r =√Mm is a good choice:• Case 1: We never meet the reserve price. Then, our regret ratio is at most r/m.• Case 2: We meet the reserve, and it eventually rises to M. Then, our regret ratio is at mostM/r.max{r/m, M/r} is minimized by s etting r/m = M/r. This gives us r =√Mm. With this choice ofr, the regret ratio ispM/m.Lecture 20: 11/01/2004 20-320.3.2 Selling in fractionsWe assume that M = 2km for some integer k.Let OPT denote the maximum price that is reached (of course, we do not know this in advance).Consider the following strategy: for each i where 1 ≤ i ≤ k, sell 1/k of our stock the first time thatthe unit price falls in the interval [2im, 2i+1m).Let j be the largest integer such that 2jm ≤OPT.Note that 2jm > OP T/2.Therefore, we sell 1/k of our stock at price at least OP T/2.So our regret ratio isOP TOP T/(2k)= 2k = 2 lg (M/m).20.3.3 A randomized reserve-price strategyWe pick i uniformly at random from 1, 2, . . . , k. We set the reserve price to 2im.Let j be the largest integer such that 2jm ≤OPT.With probability at least 1/k, we have a return of 2jm > OP T/2.Therefore, our expec ted return is at least OP T/2k.So our expec ted regret ratio is 2k = 2 lg (M/m).20.4 k-server on a lineWe have k servers on a line. A request specifies a point on the line to which a server must be moved.The cost of serving a request sequence is measured by the total distance travelled by servers. Thus,the goal is to be clever in the way servers are moved, s uch that the total distance travelled by theservers is minimized.20.4.1 A greedy strategy that isn’t competitiveA greedy strategy for this problem is to simply move the server that is closest to the requested point.However, we can easily see that this greedy strategy is not competitive. Suppose that we have twoservers A and B that are initially at points x and y, respectively, with x < y. Supp os e that ourrequests repeatedly alternate between the points y − (y − x)/4 and y + (y − x)/4. Then, accordingto the greedy strategy, all the requests will be served by B, and the total distance travelled will beinfinite. A better strategy would be to first move A and B to our two request points, in which casethe total distance travelled would be only constant.Lecture 20: 11/01/2004 20-420.4.2 Double coverageThe double coverage (DC) strategy is• If the request falls between two servers, then move both towards the request at the same rateuntil one reaches it.• Else (in which case the request falls “outside”), just move the closest server to the request.Now, we show that DC is k-competitive.We compare the moves of DC to those of an optimal offline algorithm OPT. We can assume thatOPT satisfies a request by moving exactly one se rver; we can convert any offline strategy into astrategy that move