On the Social Cost of Distributed Selfish Content Replication

TY - GEN

T1 - On the Social Cost of Distributed Selfish Content Replication

AU - Pollatos, Gerasimos G.

AU - Telelis, Orestis A.

AU - Zissimopoulos, Vassilis

N1 - Conference code: 7

PY - 2008

Y1 - 2008

N2 - We study distributed content replication networks formed voluntarily by selfish autonomous users, seeking access to information objects that originate form distant servers. Each user caters to minimization of its individual access cost by replicating locally (up to constrained storage capacity) a subset of objects, and accessing the rest form the nearest possible location. We show existence of stable networks by proving existence of pure strategy Nash equilibria for a game-theoretic formulation of this situation. Social (overall) cost of stable networks is measured by the average or by the maximum access cost experienced by any user. We study socially most and least expensive stable networks by means of tight bounds on the ratios of the Price of Anarchy and Stability respectively. Although in the worst case the ratios may coincide, we identify cases where they differ significantly. We comment on simulations exhibiting occurrence of cost-efficient stable networks on average.

AB - We study distributed content replication networks formed voluntarily by selfish autonomous users, seeking access to information objects that originate form distant servers. Each user caters to minimization of its individual access cost by replicating locally (up to constrained storage capacity) a subset of objects, and accessing the rest form the nearest possible location. We show existence of stable networks by proving existence of pure strategy Nash equilibria for a game-theoretic formulation of this situation. Social (overall) cost of stable networks is measured by the average or by the maximum access cost experienced by any user. We study socially most and least expensive stable networks by means of tight bounds on the ratios of the Price of Anarchy and Stability respectively. Although in the worst case the ratios may coincide, we identify cases where they differ significantly. We comment on simulations exhibiting occurrence of cost-efficient stable networks on average.

U2 - 10.1007/978-3-540-79549-0_17

DO - 10.1007/978-3-540-79549-0_17

M3 - Conference article

SN - 0302-9743

SP - 195

EP - 206

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - NETWORKING 2008, Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet , 7th International IFIP-TC6 Networking Conference

Y2 - 5 May 2008 through 9 May 2008

ER -