Increasing availability in a p2p storage system through a truthful taxation mechanism

Friday, 29th July 2011, 9:30 am (PDCC Discussion Room)
Speaker: Krzysztof Rzadca (University of Warsaw)
Title: Increasing availability in a p2p storage system through a truthful taxation mechanism

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 completely decentralized, peers' selfishness can greatly alter the results, leading to performance inequities that can render the system unreliable and thus ultimately unusable.

In this presentation, we show game-theoretic mechanisms that reduce the price of anarchy, i.e., the relative loss of efficiency in the decentralized matching scenario. The mechanism "taxes" the highly-available peers. A fraction of their replication slots is used by a centralized algorithm to replicate data of weakly-available peers. We prove the conditions under which the mechanism is incentive-compatible, i.e., no peer gains by artificially lowering its availability. We also experimentally show that the mechanism renders the system usable, as the data availability of weakly-available peers increases by approximately two orders of magnitude.


Krzysztof Rzadca is an assistant professor in the Institute of Informatics, University of Warsaw, Poland. He graduated with a MSc in software engineering from Warsaw University of Technology, Poland in 2004, and a PhD in computer science in 2008 jointly from Institut National Polytechnique de Grenoble (INPG), France and from Polish-Japanese Institute of Information Technology, Poland. He was French government fellowship recipient during his PhD studies. Between
2008 and 2010, he worked as a research fellow in Nanyang Technological University (NTU), Singapore.

His research focuses on resource management and scheduling in large-scale distributed systems, such as peer-to-peer systems or computational grids/clouds. He is interested in ensuring efficiency and fairness in presence of selfish users and weak central control.