On Randomized Memoryless Algorithms for the Weighted K-Server Problem

The weighted k-server problem is a generalization of the k-server problem in which the cost of moving a server of weight β_i through a distance d is β_i · d. The weighted server problem on uniform spaces models caching where caches have different write costs. We prove tight bounds on the performance of randomized memoryless algorithms for this problem on uniform metric spaces. We prove that there is an α_k competitive memoryless algorithm for this problem, where α_k = α²_k-1 + 3α_k-1 + 1; α1 = 1. On the other hand, we also prove a lower bound result, which is a strong evidence to our conjecture, that no randomized memoryless algorithm can have competitive ratio better than α_k. To prove the upper bound of α_k, we develop a framework to bound from above the competitive ratio of any randomized memoryless algorithm for this problem. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. The result is robust in the sense that a small change in the probabilities used by the algorithm results in a small change in the upper bound on the competitive ratio. The above result has two important implications. Firstly this yields an α_k-competitive memoryless algorithm for the weighted k-server problem on uniform spaces. This is the first competitive algorithm for k > 2 which is memoryless. For k = 2, our algorithm agrees with the one given by Chrobak and Sgall [1]. Secondly, this helps us prove that the Harmonic algorithm, which chooses probabilities in inverse proportion to weights, has a competitive ratio of kα_k. The only known competitive algorithm for every k before this work is a carefully crafted deterministic algorithm due to Fiat and Ricklin [2]. Their algorithm uses memory crucially- and their bound on competitive ratio more than 2^4k . Our algorithm is not only memoryless, but also has a considerably improved competitive ratio of α_k <; 1.6^2k. Further, the derandomization technique by Ben-David et al. [3] implies that there exists a deterministic algorithm for this problem with competitive ratio α²_k <; 2.56^2k.