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.