Replica placement in P2P storage : complexity and game theoretic analyses

• Main Authors: Rzadca, Krzysztof, Datta, Anwitaman, Buchegger, Sonja
• Other Authors: School of Computer Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2010
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity; DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
• Online Access: https://hdl.handle.net/10356/91297; http://hdl.handle.net/10220/6493
• Institution: Nanyang Technological University

In peer-to-peer storage systems, peers replicate each others’ data in order to increase availability. If the matching is done centrally, the algorithm can optimize data availability in an equitable manner for all participants. However, if matching is decentralized, the peers’ selfishness can greatly alter the results, leading to performance inequities that can render the system unreliable and thus ultimately unusable. We analyze the problem using both theoretical approaches (complexity analysis for the centralized system, game theory for the decentralized one) and simulation. We prove that the problem of optimizing availability in a centralized system is NP-hard. In decentralized settings, we show that the rational behavior of selfish peers will be to replicate only with similarly-available peers. Compared to the socially-optimal solution, highly available peers have their data availability increased at the expense of decreased data availability for less available peers. The price of anarchy is high: unbounded in one model, and linear with the number of time slots in the second model.