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.