Paper detail

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\cdot 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}^2+3α_{k-1}+1$; $α_1=1$. On the other hand we also prove 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. Secondly, this helps us prove that the Harmonic algorithm, which chooses probabilities in inverse proportion to weights, has a competitive ratio of $kα_k$.