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.