Cache me if you can: capacitated selfish replication games in networks

DOI10.1007/S00224-019-09939-7zbMATH Open1434.68049arXiv1007.2694OpenAlexW2966293270MaRDI QIDQ2300628FDOQ2300628

Authors: Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram 

Publication date: 27 February 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: In Peer-to-Peer (P2P) network systems, content (object) delivery between nodes is often required. One way to study such a distributed system is by defining games, which involve selfish nodes that make strategic choices on replicating content in their local limited memory (cache) or accessing content from other nodes for a cost. These Selfish Replication games have been introduced in [8] for nodes that do not have any capacity limits, leaving the capacitated problem, i.e. Capacitated Selfish Replication (CSR) games, open. In this work, we first form the model of the CSR games, for which we perform a Nash equilibria analysis. In particular, we focus on hierarchical networks, given their extensive use to model communication costs of content delivery in P2P systems. We present an exact polynomial-time algorithm for any hierarchical network, under two constraints on the utility functions: 1) "Nearer is better", i.e. the closest the content is to the node the less its access cost is, and 2) "Independence of irrelevant alternatives", i.e. aggregation of individual node preferences. This generalization represents a vast class of utilities and more interestingly allows each of the nodes to have simultaneously completely different functional forms of utility functions. In this general framework, we present CSR games results on arbitrary networks and outline the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. Moreover, we prove that the problem of equilibria existence becomes NP-hard for general CSR games.

Full work available at URL: https://arxiv.org/abs/1007.2694

Recommendations

• Cache me if you can: capacitated selfish replication games
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
• Selfish caching in distributed systems, a game-theoretic analysis
• On the topologies formed by selfish peers
• Topological implications of selfish neighbor selection in unstructured peer-to-peer networks

zbMATH Keywords

computational complexitygame theorychoice theoryhierarchical networkscachingdistributed networkspreference orders

Mathematics Subject Classification ID

Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cites Work

• Social choice and individual values
• Algorithmic Game Theory
• Worst-case equilibria
• Title not available (Why is that?)
• Permanents, Pfaffian orientations, and even directed circuits
• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A course in game theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation Algorithms for Data Placement Problems
• Raptor codes
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• Title not available (Why is that?)
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Settling the complexity of computing two-player Nash equilibria
• The Online Median Problem
• On a network creation game
• The complexity of computing a Nash equilibrium
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Selfish caching in distributed systems, a game-theoretic analysis
• Cache me if you can: capacitated selfish replication games
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
• Placement algorithms for hierarchical cooperative caching
• Mistreatment-resilient distributed caching
• Optimal data placement on networks with a constant number of clients
• Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game
• Title not available (Why is that?)

Cited In (4)

• Selfish caching in distributed systems, a game-theoretic analysis
• Cache me if you can: capacitated selfish replication games
• Give-and-take based peer-to-peer content distribution networks
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game

This page was built for publication: Cache me if you can: capacitated selfish replication games in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300628)