Change search
ReferencesLink to record
Permanent link

Direct link
Replica Placement in P2P Storage:: Complexity and Game Theoretic Analyses
NTU Singapore.
NTU Singapore.
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-5742-5462
2010 (English)In: Proceedings - International Conference on Distributed Computing Systems, 2010, 599-609 p.Conference paper (Refereed)
Abstract [en]

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. We also propose centralized and decentralized heuristics that, according to our experiments, converge fast in the average case. The high price of anarchy means that a completely decentralized system could be too emph{hostile} for peers with low availability, who could never achieve satisfying replication parameters. Moreover, we experimentally show that even explicit consideration and exploitation of diurnal patterns of peer availability has a small effect on the data availability—except when the system has truly global scope. Yet a fully centralized system is infeasible, not only because of problems in information gathering, but also the complexity of optimizing availability. The solution to this dilemma is to create system-wide cooperation rules that allow a decentralized algorithm, but also limit the selfishness of the participants

Place, publisher, year, edition, pages
2010. 599-609 p.
, IEEE International Conference on Distributed Computing Systems, ISSN 1063-6927
Keyword [en]
price of anarchy, equitable optimization, distributed storage, peer-to-peer, social networks
National Category
Computer and Information Science
Research subject
URN: urn:nbn:se:kth:diva-55883DOI: 10.1109/ICDCS.2010.67ISI: 000286945900059ScopusID: 2-s2.0-77955881883ISBN: 978-076954059-7OAI: diva2:472005
30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010; Genova; Italy; 21 June 2010 through 25 June 2010
Swedish Research Council

QC 20150713

Available from: 2012-01-03 Created: 2012-01-03 Last updated: 2015-07-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Buchegger, Sonja
By organisation
Theoretical Computer Science, TCSACCESS Linnaeus Centre
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link