论文标题
使用Glauber动力学和拍卖的非金属数据放置问题的分布式计算
Distributed Computation for the Non-metric Data Placement Problem using Glauber Dynamics and Auctions
论文作者
论文摘要
我们考虑了非金属数据放置问题，并开发用于计算或近似其最佳积分解决方案的分布式算法。我们首先表明，非金属数据放置问题是不适合对数因素的不合适性。然后，我们提供了目标函数的游戏理论分解，并表明自然的Glauber动力学，其中玩家以与从缓存这些资源中获得的效用成正比的概率更新其资源，将融合到最佳的全球解决方案，以获得足够大的噪声参数。特别是，我们在一定的噪声参数中建立了Glauber动力学的多项式混合时间。最后，我们提供了另一种基于拍卖的分布式算法，该算法使我们能够通过绩效保证近似最佳的全球解决方案，该解决方案取决于收入与从基础拍卖中获得的收入与社会福利的比率。我们的结果提供了第一个分布式计算算法，以解决非金属数据放置问题。
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.
