Selfish caching in distributed systems: a game-theoretic analysis

ABSTRACT

We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources or cost for access to a remote replica. We show the existence of pure strategy Nash equilibria and investigate the price of anarchy, which is the relative cost of the lack of coordination. The price of anarchy can be high due to undersupply problems, but with certain network topologies it has better bounds. With a payment scheme the game can always implement the social optimum in the best case by giving servers incentive to replicate.

REFERENCES

• 1: http://www.mosek.com.
• 2: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 3: Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780617]
• 4: Yan Chen , Randy H. Katz , John Kubiatowicz, SCAN: A Dynamic, Scalable, and Efficient Content Distribution Network, Proceedings of the First International Conference on Pervasive Computing, p.282-296, August 26-28, 2002
• 5: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: Peter Danzig, NetCache architecture and deployment, Computer Networks and ISDN Systems, v.30 n.22-23, p.2081-2091, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00250-5]
• 7: Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779942]
• 8: John R. Douceur , Roger P. Wattenhofer, Large-Scale Simulation of Replica Placement Algorithms for a Serverless Distributed File System, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.311, August 15-18, 2001
• 9: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 10: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Michel Goemans , Li Erran Li , Vahab S. Mirrokni , Marina Thottan, Market sharing games applied to content distribution in ad-hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989467]
• 13: Michel X. Goemans , Martin Skutella, Cooperative facility location games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.76-85, January 09-11, 2000, San Francisco, California, United States
• 14: S. Gribble et al. What Can Databases Do for Peer-to-Peer? In WebDB Workshop on Databases and the Web, June 2001.
• 15: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 16: Sitaram Iyer , Antony Rowstron , Peter Druschel, Squirrel: a decentralized peer-to-peer web cache, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571861]
• 17: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 18: S. Jamin et al. On the Placement of Internet Instrumentation. In Proc. of IEEE INFOCOM, pages 295--304, 2000.
• 19: S. Jamin et al. Constrained Mirror Placement on the Internet. In Proc. of IEEE INFOCOM, pages 31--40, 2001.
• 20: Bong-Jun Ko, Distributed, Self-Stabilizing Placement of Replicated Resources in Emerging Networks, Proceedings of the 11th IEEE International Conference on Network Protocols, p.6, November 04-07, 2003
• 21: E. Koutsoupias and C. Papadimitriou. Worst-Case Equilibria. In STACS, 1999.
• 22: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 23: B. Li, M. J. Golin, G. F. Italiano, and X. Deng. On the Optimal Placement of Web Proxies in the Internet. In Proc.of IEEE INFOCOM, 1999.
• 24: Mohammad Mahdian , Yinyu Ye , Jiawei Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.229-242, September 17-21, 2002
• 25: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: Universal Topology Generation from a User''s Perspective, Boston University, Boston, MA, 2001
• 26: R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
• 27: P. B. Mirchandani and R. L. Francis. Discrete Location Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization, 1990.
• 28: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 29: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 30: L. Qiu, V. N. Padmanabhan, and G. M. Voelker. On the Placement of Web Server Replicas. In Proc. of IEEE INFOCOM, 2001.
• 31: A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.101, May 31-June 04, 1999
• 32: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 33: Yasushi Saito , Christos Karamanolis , Magnus Karlsson , Mallik Mahalingam, Taming aggressive replication in the Pangaea wide-area file system, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060292]
• 34: Xueyan Tang , Samuel T. Chanson, Coordinated En-Route Web Caching, IEEE Transactions on Computers, v.51 n.6, p.595-607, June 2002 [doi>10.1109/TC.2002.1009146]
• 35: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 36: E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to Model an Internetwork. In Proc. of IEEE INFOCOM, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Economics, Performance, Theory

Keywords:
Nash equilibria, caching, distributed systems, game-theoretic models, peer-to-peer systems, price of anarchy