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 memory less algorithms for this problem on uniform metric spaces. We prove that there is an α_k competitive memory less algorithm for this problem, where α_k=α_k-12+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 memory less 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 memory less 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 memory less algorithm for the weighted k-server problem on uniform spaces. This is the first competitive algorithm for k>2 which is memory less. For k=2, our algorithm agrees with the one given by Chrobak and Sgall. 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. Their algorithm uses memory crucially and their bound on competitive ratio more than 24k. Our algorithm is not only memory less, but also has a considerably improved competitive ratio of α_k

Authors

• Ashish Chiplunkar
• Sundar Vishwanathan

Keywords

• Servers
• Upper bound
• Equations
• Extraterrestrial measurements
• Probability distribution
• Linear systems
• Memoryless
• Server Problem
• Linear System
• Algorithm For Problem
• Uniform Spacing
• Competitive Algorithm
• Competitive Ratio
• Lower Bound
• Linear Programming
• Potential Increase
• Decrease In Potential
• Extreme Points
• Maximum Norm
• Online Algorithm
• Largest Element
• Sequence Of Real Numbers
• Triangular Part
• Sequence Of Positive Numbers
• Weighted k-server
• Memoryless Randomized Algorithms