Distributed Data Placement and Content Delivery in Web Caches with Non-Metric Access Costs

Motivated by applications in web caches and content delivery in peer-to-peer networks, we consider the non-metric data placement problem and develop distributed algorithms for computing or approximating its optimal solutions. In this problem, the goal is to store copies of the data points among a set of cache-capacitated servers to minimize overall data storage and clients' access costs. We first show that the non-metric data placement problem is inapproximable up to a logarithmic factor. We then provide a game-theoretic decomposition of the objective function and show that a natural type of Glauber dynamics in which servers update their cache contents with probability proportional to the utility they receive from caching those data will converge to an optimal global solution for a sufficiently large noise parameter. In particular, we establish the polynomial mixing time of the Glauber dynamics for a certain range of noise parameters. Such a game-theoretic decomposition not only provides a good performance guarantee in terms of content delivery but also allows the system to operate in a fully distributed manner, hence reducing its computational load and improving its robustness to failures. Moreover, we provide another auction-based distributed algorithm, which allows us to approximate the optimal solution with a performance guarantee that depends on the ratio of the revenue vs. social welfare obtained from the underlying auction.