Header menu link for other important links
X
Cache Me if You Can: Capacitated Selfish Replication Games in Networks
Ragavendran Gopalakrishnan, Naga Naresh Karuturi,
Published in Springer
2020
Volume: 64
   
Issue: 2
Pages: 272 - 310
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 Chun et al. (2004) 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. By adding some constraints in the number of objects and their preferences, we show that the equilibrium can be found in polynomial time. Finally, we introduce the fractional version of CSR games (F-CSR) to represent content distribution. We prove that equilibrium exists for every F-CSR game, but it is PPAD-complete. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.
About the journal
JournalData powered by TypesetTheory of Computing Systems
PublisherData powered by TypesetSpringer
ISSN14324350
Open AccessYes
Concepts (14)
  •  related image
    Computational complexity
  •  related image
    Game theory
  •  related image
    Hierarchical systems
  •  related image
    Peer to peer networks
  •  related image
    Polynomial approximation
  •  related image
    Caching
  •  related image
    CHOICE THEORY
  •  related image
    Content distribution
  •  related image
    DISTRIBUTED NETWORKS
  •  related image
    Hierarchical network
  •  related image
    INDEPENDENCE OF IRRELEVANT ALTERNATIVES
  •  related image
    PEER TO PEER (P2P) NETWORK
  •  related image
    Polynomial-time algorithms
  •  related image
    Distributed computer systems