Allocating Objects in a Network of Caches: Centralized and Decentralized Analyses
分析协作缓存网络中对象的分配问题，发现集中式场景下最优社会福利可通过运输问题求解，分散式场景下存在纯均衡且有限步内可达，并设计拍卖机制激励缓存持有对象以达到最优社会福利。
We analyze the allocation of objects in a network of caches that collaborate to service requests from customers. A thorough analysis of this problem in centralized and decentralized setups, both of which occur in practice, is essential for understanding the benefits of collaboration. A key insight offered by this paper is that an efficient implementation of cooperative cache management is possible because, in the centralized scenario, the object allocation resulting in the best social welfare can be found easily as a solution to a transportation problem. For the decentralized scenario involving selfish caches, it is shown that pure equilibria exist and that the cache network always reaches a pure equilibrium in a finite number of steps, starting from any point in the strategy space. An auction mechanism is developed to derive prices that motivate the caches to hold objects in a manner such that the optimal social welfare is attained. In the special case of symmetric caches, simple algorithms are devised to find the optimal social welfare allocation, the best pure equilibrium, and the prices for sharing objects. The results obtained in this paper should be valuable in developing and evaluating cache-management policies. Resource-sharing problems with a similar cost structure exist in a variety of other domains, and the insights gained here are expected to extend to those scenarios as well.