Selfish Content Replication on Graphs
2011 (English)In: ITC '11 Proceedings of the 23rd International Teletraffic Congress, ITCP , 2011, 119-126 p.Conference paper (Refereed)
Replication games are a model of the problem of content placement in computer and communication systems, when the participating nodes make their decisions such as to maximize their individual utilities. In this paper we consider replication games played over arbitrary social graphs; the social graph models limited interaction between the players due to, e.g., the network topology. We show that in replication games there is an equilibrium object placement for arbitrary social graphs. Nevertheless, if all nodes follow a myopic strategy to update their object placements then they might cycle arbitrarily long before reaching an equilibrium if the social graph is non-complete. We give sufficient conditions under which such cycles do not exist, and propose an efficient distributed algorithm to reach an equilibrium over a non-complete social graph.
Place, publisher, year, edition, pages
ITCP , 2011. 119-126 p.
Engineering and Technology
Research subject SRA - ICT
IdentifiersURN: urn:nbn:se:kth:diva-47473ScopusID: 2-s2.0-80054981267ISBN: 978-0-9836283-0-9OAI: oai:DiVA.org:kth-47473DiVA: diva2:455465
2011 23rd International Teletraffic Congress, ITC 2011. San Francisco, CA. 6 September 2011 - 9 September 2011
FunderSwedish Research Council
QC 201111152012-02-062011-11-102012-02-06Bibliographically approved