Allocating Objects in a Network of Caches: Centralized and Decentralized Analyses

Mohit Tawarmalani (), Karthik Kannan () and Prabuddha De ()
Additional contact information
Mohit Tawarmalani: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
Karthik Kannan: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
Prabuddha De: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907

Management Science, 2009, vol. 55, issue 1, 132-147

Abstract: 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.

Keywords: collaborative cache management; resource sharing; peer-to-peer network; mathematical programming; game theory (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1080.0923 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:55:y:2009:i:1:p:132-147

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().