  We consider the non-metric data placement problem and develop distributed
algorithms for computing or approximating its optimal integral solution. 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 natural Glauber dynamics in which players
update their resources with probability proportional to the utility they
receive from caching those resources 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. Finally, we provide another auction-based distributed algorithm,
which allows us to approximate the optimal global solution with a performance
guarantee that depends on the ratio of the revenue vs. social welfare obtained
from the underlying auction. Our results provide the first distributed
computation algorithms for the non-metric data placement problem.
