Contents pg01: The server problem as a metrical task system. Finiteness. Apr 6 04:37 2002 pg02: The Double Cover algorithm for the k-server problem on the line. Mar 13 14:08 2002 pg03: A lower bound of k for the deterministic competitiveness of the k-server problem. Mar 20 13:48 2002 pg04: A lower bound of H_k for the randomized competitiveness of the k-server problem. [Available later.] pg05: HARMONIC, a memoryless randomized online algorithm for the k-server problem. Apr 1 15:50 2002 pg06: Random Slack, a memoryless randomized online algorithm for the k-server problem. [Under construction.] Apr 6 04:20 2002 The Server Problem as a Metrical Task System. Apr 6 04:37 2002 Let M be a metric space. Let M' be the set of all unordered k-tuples in M. Then M' is also a metric space under minimum matching. That is, if X and Y are unordered k-tuples in M, we can define ||X,Y|| to be the smallest value of Sum_i{||x_i,y_i||} that can be obtained by writing X = {x_1, ... x_k} and Y = {y_1, ... y_k}. The k-server problem in M is then the task system (M',calT) defined as follows. Although it is abuse of notation, if r is a point in M, we use r also as the name of a task in calT, defined as follows: if X in M', i.e., X is an unordered k-tuple of points in M, let r(X) = 0 if r in X, and let r(X) = infinity otherwise. (It is common practice to use the same name to describe two distinct things, even in the same formula. This saves space. To avoid overloading, we could use "tau_r" for the name of the task r, but then, later, we would regret this, since we would be obligated to write "tau," a symbol which would then convey no additional information beyond the first use, many times.) Note that the server problem in M is a forcing metrical task system. Finiteness. A number of proofs implicitly assume that there are only finitely many states. This means that, technically, these proofs are invalid if there are infinitely many states, for example, for the k-server problem on the line, or on any infinite space. It turns out that, in most cases, this is a mere technicality. I will briefly indicate in class why we do not need to worry about this in most cases, which include all practical applications. The Double Cover Algorithm (DC) for the k-server problem on the line. Mar 13 14:08 2002 Suppose that s_1, ... s_k are the positions of k servers on the line. Without loss of generality, s_i is to the left of s_i+1. If r is a request, move either one or two servers as follows: 1. If r = s_i, do nothing. 2. If r is to the left of s_1, move the leftmost server from s_1 to r. 3. If r is to the right of s_k, move the rightmost server from s_k to r. 4. If r is strictly between s_i and s_i+1 for some i, then move the two servers toward r at the same speed until one of them reaches r, at which time the other stops moving. Theorem: DC is k-competitive. Theorem: If M is a metric space with k+1 points, there is no deterministic algorithm for the k-server problem on M whose competitiveness is less than k. Proof: Let the points of M be x_0, x_1, ... x_k. We can assume that the servers start on x_1, ... x_k. Let A be an arbitrary deterministic online algorithm. We define k different deterministic offline algorithms, which we call B_1, ... B_k. The idea of the proof is that A's cost is equal to the sum of the costs of the B_i, except for a constant. Initially, each B_i has its servers on all points except x_0. At each step, the request is to the one point where A does not have a server. Let r^1, r^2, ... r^n be the request sequence; r^1 = x_0. Note that A serves the request at step t by moving a server from r^t+1 to r^t. The loop invariant is that each point other than the last request point is covered by all but one of the B_i. The loop invariant holds after each step. The initial request is to x_0. Each B_i serves that request by moving a server from x_i to x_0. The loop invariant is thus established. At step t, for t > 0, there is just one of the B_i that does not have a server at r^t. That B_i then moves its server from r^t-1 to r^t to serve the request. Note that, for all but the initial step, the cost for A is exactly the total cost of all k of the B_i. Thus, the average B_i has cost 1/k times the cost of A plus the initial cost. It follows that at least one of the B_i has cost at most 1/k times the cost of A plus a constant. HARMONIC, a memoryless randomized algorithm for the k-server problem. Apr 1 15:50 2002 Given that the servers are in positions s_1, ... s_k, and the request is r, HARMONIC behaves as follows: If r = s_i for some i, do nothing. Otherwise, for each i, move the server from s_i to r with probability p_i, where: n_i = 1/r_i for each i n = n_1 + ... n_k p_i = n_i/n for each i. Note that the sum of the p_i is 1. Let C_k be the competitiveness of HARMONIC for the k-server problem. It is known that C_k >= k(k+1)/2 (this is in the textbook). For k = 2, this is known to be an upper bound as well. Thus, C_2 = 3. Random_Slack, a memoryless randomized algorithm for the 2-server problem. Apr 6 04:20 2002 Given that the servers are in positions s_1, s_2, and the request is r, Random_Slack behaves as follows: If r = s_i for some i, do nothing. Otherwise, for each i, move the server from s_i to r with probability p_i, where: a = (||s_1,s_2||+||s_1,r||-||s_2,r||)/2 b = (||s_1,s_2||+||s_2,r||-||s_1,r||)/2 p_1 = b/(a + b) p_2 = a/(a + b) Theorem: Random_Slack is 2-competitive. Proof: We give a behavioral 2-potential Phi. Let the special pairs be all (chi_x,x), where x is any state, i.e., pair of points, and where chi_x is the cone on x, i.e., chi_x(z) = ||x,z|| if z is any state (i.e., pair). If x = {s_1,s_2}, define |x| = ||s_1,s_2||, the distance between the points, and define Phi(chi_x,x) = |x|. (It is not necessary to define Phi for any other pair.) Condition 2. is trivial. We now verify Condition 1. Suppose (chi_x,x) is a special pair, x = {s_1,s_2}, and r is a request point. Let e_1, e_2 be defined as in the algorithmic description above. Let x_1 = {r,s_2}, and x_2 = {r,s_1} (This seems backwards; but it's not. If we move the server from s_i, the configuration of the two servers is x_i, as it should be.) Let w_i = chi_{x_i}, the cone on x_i. Then Phi_i = Phi(w_i,x_i) = |x_i|, which is d(r,s_2) if i=1, d(r,s_1) if i = 2. Let lambda_i = p_i as given in the algorithmic description. Let K = (||r,s_1||+||r,s_2||-||s_1,s_2||)/2. We need to show that lambda_1*w_1(z) + lambda_2*w_2(z) + K <= w'(z) for any state z, where w' = chi_x update r. It suffices to show it for z = x_1 or x_2, since those are the only support points of w'. The needed verifications will be omitted, as they are routine. We also need to show that Phi(chi_x) >= lambda_1*Phi(w_1,x_1)+lambda_2*Phi(w_2,x_2)-2K. This is also routine. This concludes the proof that Random_Slack is 2-compeititive against the adaptive online adversary. (It follows immediately that Random_Slack is 2-competitive against the oblivious adversary.) We note that no randomized online algorithm for the k-server problem can have competitiveness lower than k against the adaptive online adversary, as the adversary, knowing the positions of the algorithm's servers after each move, can use the so-called "cruel request sequence," if the space has k+1 points. Thus, Random_Slack is optimal against that adversary. Random_Slack, a memoryless randomized algorithm for the 2-server problem. Given that the servers are in positions s_1, s_2, and the request is r, Random_Slack behaves as follows: If r = s_i for some i, do nothing. Otherwise, for each i, move the server from s_i to r with probability p_i, where: e_1 = d(s_1,s_2)+d(s_1,r)-d(s_2,r) e_2 = d(s_1,s_2)+d(s_2,r)-d(s_1,r) p_1 = e_2 / (e_1 + e_2) p_2 = e_1 / (e_1 + e_2) Theorem: Random_Slack is 2-competitive. Proof: We give a behavioral 2-potential Phi. If x = {s_1,s_2} and w is a cone on x, i.e., w is supported by x, define Phi(w,x) = ||s_1,s_2|| - 2w(x). For any w which is not a cone, define Phi(w,x) to be infinite. (To obey the rule that Phi must have a finite real value, we could instead define it to be any number large enough that the update condition holds trivially.) We need to prove the conditions: 1. If w' = w update r, and if x is a state, then there exist work functions w_1, w_2, states x_1, x_2, and probabilities lambda_1 , lambda_2, where Sum_i lambda_i = 1, such that 1(a). For any state z, Sum_i lambda_i w_i(z) <= w'(z) 1(b). Phi(w,x) >= Sum_i lambda_i*{||x,x_i||+r(x_i)+Phi(w_i,x_i)} 2. If K is a constant, Phi(w,x) = Phi(w+K,x) + 2*K. We only need to consider the case where w is a cone on x. Condition 2., the offset condition, is trivial. We now look at Condition 1. Let lamba_1 = p_1 and lambda_2 = p2, as given by the formulas above. Let x_1 = {s_2,r} and x_2 = {s_1,r} Let w_1 be the cone on x_1 such that w_1(x_1) = ||s_1,r||, and let w_2 be the cone on x_2 such that w_2(x_2) = ||s_2,r||. It is routine to verify that 1(a) holds for z = x_1 and for z = x_2. Since w' is supported by {x_1,x_2}, the Lipschitz property of work functions guarantees that 1(a) holds for all other states. 1(b) is proved by routine algebra. This completes the proof.