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.
翻译:我们考虑了非计量数据放置问题,并开发了用于计算或接近其最佳整体解决方案的分布式算法。我们首先显示,非计量数据放置问题无法被接受到一个对数因素。然后我们提供了客观功能的游戏理论分解,并表明,自然的Grauber动态,其中玩家更新资源的可能性与其从缓存这些资源中获得的效用成正比,从而将汇集到一个最佳的全球解决方案中,以获得足够大的噪音参数。特别是,我们为一定范围的噪音参数建立了格拉贝动力的多元混合时间。最后,我们提供了另一个基于拍卖的分布式算法,使我们能够接近最佳全球解决方案,其性能保证取决于从基本拍卖中获得的收入与社会福利的比例。我们的结果为非计量数据放置问题提供了第一个分布式计算算法。