Report

Competitive Paging Algorithms Amos Fiat, Richard Karp, Michael Luby, Lyle McGeoch, Daniel Sleator, Neal Young presented by Seth Phillips Overview Introduction Server Problems Marking Algorithm EATR Lower Bound Competitive Against Other Algorithms Introduction – Paging Problem System with k pages of fast memory (cache/RAM) Has n-k pages of slow memory (RAM/virtual) Requesting a page not in fast memory Eject a page to make room (page fault) Online paging algorithm Decision made without knowledge of future requests Performance analyzed against off-line algorithm – complete knowledge Deterministic algorithms are k-competitive Randomized Algorithms Analyzed as a sum cost of the algorithm Cost on a sequence of input averaged over all the random choices that the algorithm makes while processing the sequence Overview Introduction Server Problems Marking Algorithm EATR Lower Bound Competitive Against Other Algorithms K-server Problem Let G be an n-vertex graph with positive edge lengths obeying the triangle inequality Let k mobile servers occupy vertices of G Given a sequence of requests, each of which specifies a vertex, decide how to move the servers in response to each request K-server continued Requests must be satisfied in order of their occurrence in the sequence Cost of handling a sequence is equal to the total distance moved by the servers It is conjectured that there exists a k-competitive k-server algorithm for any graph Uniform k-server problem Cost of moving a server from any vertex to any other vertex is 1 Isomorphic to the paging problem: any vertex with a server is in fast memory and the vertices of the graph represent the address space Overview Introduction Server Problems Marking Algorithm EATR Lower Bound Competitive Against Other Algorithms Marking Algorithm Randomized algorithm for uniform k-server problem on graph with n vertices Servers are initially on vertices 1 through k Algorithm maintains a set of marked vertices Initially these are the vertices covered by the servers Marking Each time a vertex is requested, it is marked If k+1 vertices are marked, all marks except the most recently requested vertex are erased Serving If vertex is covered, then no servers move If vertex is not covered, then a server is chosen uniformly at random from the unmarked vertices That server is moved to cover Competitiveness 2*H_k competitive (H_k on the order of ln(k)) Algorithm implicitly divides request sequence into phases. First phase begins with r(i), where I is the smallest integer such that r(i) is not in the set {1 through k}. Comp. continued In general the phase starting with r(i) ends with r(j) j is the smallest integer such that the set {r(i), r(i+1), . . ., r(j+1)} has cardinality k+1 Comp. continued Implicitly the first request of every phase is made to an unmarked vertex A vertex is clean if it was not requested in the previous phase and has not yet been requested in this phase – we’ll say there are l of these A vertex is stale if it was requested in the previous phase and has not yet been requested in this phase Adversary Amortized Cost At least l/2 because: Let d be the number of servers that do not coincide with marking’s at the beginning of the phase Let d’ be this quantity at the end of the phase Cost(A) >= l – d because l requests have to be met, mitigated by a possible d different server locations Adversary Cost Continued C(Adv) >= d’ because: The vertices of S are those covered by Marking at the end of the phase, so d’ servers are not in S Since Adversary is lazy (does not unnecessarily move servers) at least d’ of A’s servers were outside of S for the entire phase Adversary Cost Continued C(Adv) >= max(l – d, d’) >= ½(l – d + d’) D and d’ naturally telescope so simply C(Adv) >= l/2 Marking Expected Cost l requests to clean vertices – each costs 1 k – l requests to stale vertices – each based on the probability that there is no server there Highest cost is when the l requests to clean vertices come first (allows the most stale vertices to be reassigned) That leaves the cost of the k-l stales to be: l/k + l/(k-1) + l/(k-2) + .. . + l/(l+1) = l*(H_k – H_l) Final Cost Competitiveness l*H_k – l*H_l + l <= l*H_k Since the cost of the adversary is l/2: The Marking algorithm is 2*H_k competitive For the n-1 server problem it is H_n-1 competitive, but for time constraints I’ll skip this Overview Introduction Server Problems Marking Algorithm EATR Lower Bound Competitive Against Other Algorithms EATR Stands for End After Twice Requested This is an algorithm specific to the uniform 2server problem Servers initially on vertices 1 + 2 Stale redefined to not clean and not the most recently requested vertex When a stale vertex is requested, the servers are placed on the two most recently requested vertices EATR Analysis Let l be the number of clean vertices requested during a phase The number of stale vertices before the request that terminates the phase is l+1 The probably of a server on each of these is 1/(l+1) The expected cost of each phase is l + l/(l+1) Adversary Analysis The best possible cost incurred by any algorith for each phase is at least l The competitive factor is therefore: (l + l/(l+1))/l = 1 + 1/(l+1) <= 3/2 Overview Introduction Server Problems Marking Algorithm EATR Lower Bound Competitive Against Other Algorithms Lower Bound There is no c-competitive randomized algorithm for the uniform (n-1) server problem on n vertices with c < H_n-1 (Time constraints) The article proves this, which also makes the marking algorithm in a class of best possible algorithms for this problem Overview Introduction Server Problems Marking Algorithm EATR Lower Bound Competitive Against Other Algorithms Algorithms Competitive Against Several Others Adopt a viewpoint where each algorithm is tailored for a specific choice of k and n. The ordered pair (k, n) is called the type of algorithm Let A be adeterministic and B be a deterministic on-line algorithms of the same type and c be a positive constant If for every sequence r of requests C_A(r) <= c*C_B(r) + alpha then A is c-competitive with B ACASO continued Let c* = (c(1), c(2), . .. C(m)) be a sequence of postive real numbers c* is realizable if, for every (k,n) and every sequence B(1), B(2) . . .B(m) there exists an algorithm A of type (k,n) such then A is c(i) competitive with B(i) c* realizable iff: Sum from 1 to m of (1/c(i)) <= 1