ABSTRACT
Distributed systems without a central authority, such as peer-to-peer (P2P) systems, employ incentives to encourage nodes to follow the prescribed protocol. Game theoretic analysis is often used to evaluate incentives in such systems. However, most game-theoretic analyses of distributed systems do not adequately model the repeated interactions of nodes inherent in such systems. We present a game-theoretic analysis of a popular P2P protocol, Bit-Torrent, that models the repeated interactions in such protocols. We also note that an analytical approach for modeling incentives is often infeasible given the complicated nature of most deployed protocols. In order to comprehensively model incentives in complex protocols, we propose a simulation-based method, which we call Design Space Analysis (DSA). DSA provides a tractable analysis of competing protocol variants within a detailed design space. We apply DSA to P2P file swarming systems. With extensive simulations we analyze a wide-range of protocol variants and gain insights into their robustness and performance. To validate these results and to demonstrate the efficacy of DSA, we modify an instrumented BitTorrent client and evaluate protocols discovered using DSA. We show that they yield higher system performance and robustness relative to the reference implementation.
Supplemental Material
- R. Axelrod. The Evolution of Cooperation. Basic Books, New York, 1984.Google Scholar
- A. Bharambe, C. Herley, and V. Padmanabhan. Analyzing and improving a BitTorrent network's performance mechanisms. In INFOCOM, 2006.Google Scholar
- C. Buragohain, D. Agrawal, and S. Suri. A game theoretic framework for incentives in P2P systems. In IEEE P2P, 2003. Google ScholarDigital Library
- A.L.H. Chow, L. Golubchik, V. Misra. BitTorrent: An extensible heterogeneous model. In INFOCOM, 2009.Google Scholar
- R. Dash, N. Jennings, and D. Parkes. Computational-mechanism design: A call to arms. IEEE Intelligent Systems, 18:40--47, 2003. Google ScholarDigital Library
- J. Feigenbaum and S. Shenker. Distributed Algorithmic Mechanism Design: Recent Results and Future Directions. In ACM DIALM, 2002. Google ScholarDigital Library
- M. Feldman, K. Lai, I. Stoica, and J. Chuang. Robust incentive techniques for peer-to-peer networks. In ACM EC, pp. 102--111, 2004. Google ScholarDigital Library
- R. Hahnel and A. Library. The ABCs of political economy: A modern approach. Pluto Press, 2002.Google Scholar
- T. Hoßfeld, F. Lehrieder, D. Hock, S. Oechsner, Z. Despotovic, W. Kellerer, and M. Michel. Characterization of BitTorrent swarms and their distribution in the Internet. Computer Networks, 55:1197--1215, 2011. Google ScholarDigital Library
- D. Hruschka and J. Henrich. Friendship, cliquishness, and the emergence of cooperation. Journal of Theoretical Biology, 239:1--15, 2006.Google ScholarCross Ref
- R. Izhak-Ratzin. Collaboration in BitTorrent systems. In IFIP-TC Networking, pp. 338--351, 2009. Google ScholarDigital Library
- S. Jun and M. Ahamad. Incentives in BitTorrent induce free riding. In P2PECON, 2005.Google ScholarDigital Library
- A.-M. Kermarrec and M. van Steen, editors. ACM SIGOPS Operating Systems Review 41, Special Issue on Gossip-Based Networking. 2007.Google Scholar
- A. Legout, N. Liogkas, E. Kohler, and L. Zhang. Clustering and sharing incentives in bittorrent systems. In ACM SIGMETRICS, pp. 301--312, 2007. Google ScholarDigital Library
- B. Leong, Y. Wang, S. Wen, C. Carbunaru, Y. Teo, C. Chang, and T. Ho. Improving peer-to-peer file distribution: winner doesn't have to take all. In ACM APSys, pp. 55--60, 2010. Google ScholarDigital Library
- D. Levin, K. LaCurts, N. Spring, and B. Bhattacharjee. BitTorrent is an auction: analyzing and improving BitTorrent's incentives. In ACM SIGCOMM, 2008. Google ScholarDigital Library
- T. Locher, P. Moor, S. Schmid, and R. Wattenhofer. Free riding in BitTorrent is cheap. In HotNets-V, 2006.Google Scholar
- R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Experiences applying game theory to system design. In ACM PINS, pp. 183--190, 2004. Google ScholarDigital Library
- G. Mailath. Do people play Nash equilibrium? Lessons from evolutionary game theory. Journal of Economic Literature, 36:1347--1374, 1998.Google Scholar
- M. Meulpolder, J. Pouwelse, D. Epema, and H. Sips. BarterCast: A practical approach to prevent lazy freeriding in P2P networks. In IEEE IPDPS, 2009. Google ScholarDigital Library
- J. Mol, J. Pouwelse, M. Meulpolder, D. Epema, and H. Sips. Give-to-get: Free-riding-resilient video-on-demand in p2p systems. In SPIE/ACM MMCN, 2008.Google Scholar
- M. Osborne and A. Rubinstein. A course in game theory. The MIT press, 1994.Google Scholar
- F. Pianese, J. Keller, and E. Biersack. PULSE, a flexible P2P live streaming system. In INFOCOM, 2006.Google ScholarCross Ref
- M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in BitTorrent. In NSDI, 2007. Google ScholarDigital Library
- M. Posch. Win-Stay, Lose-Shift Strategies for Repeated Games--Memory Length, Aspiration Levels and Noise. Journal of Theoretical Biology, 198:183--195, 1999.Google ScholarCross Ref
- D. Qiu and R. Srikant. Modeling and performance analysis of BitTorrent-like peer-to-peer networks. ACM SIGCOMM Computer Communication Review, 34:367--378, 2004. Google ScholarDigital Library
- A. Rao, A. Legout, and W. Dabbous. Can Realistic BitTorrent Experiments Be Performed on Clusters? In IEEE P2P, 2010.Google Scholar
- E. Rasmusen. Games and information: An introduction to game theory. Wiley-Blackwell, 2007.Google Scholar
- T. Roughgarden and É. Tardos. How bad is selfish routing. Journal of the ACM, 49:236--259, 2002. Google ScholarDigital Library
- K. Rzadca, A. Datta, and S. Buchegger. Replica placement in p2p storage: Complexity and game theoretic analyses. In ICDCS, pp. 599--609, 2010. Google ScholarDigital Library
- S. Shenker. Making greed work in networks: A game-theoretic analysis of switch service disciplines. IEEE/ACM Transactions on Networking, 3:819--831, 2002. Google ScholarDigital Library
- M. Yang, Z. Zhang, X. Li, and Y. Dai. An empirical study of free-riding behavior in the Maze P2P file-sharing system. Peer-to-Peer Systems IV, pp. 182--192, 2005. Google ScholarDigital Library
Index Terms
Design space analysis for modeling incentives in distributed systems
Recommendations
Design space analysis for modeling incentives in distributed systems
SIGCOMM '11Distributed systems without a central authority, such as peer-to-peer (P2P) systems, employ incentives to encourage nodes to follow the prescribed protocol. Game theoretic analysis is often used to evaluate incentives in such systems. However, most game-...
Bittorrent is an auction: analyzing and improving bittorrent's incentives
SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communicationIncentives play a crucial role in BitTorrent, motivating users to upload to others to achieve fast download times for all peers. Though long believed to be robust to strategic manipulation, recent work has empirically shown that BitTorrent does not ...
Bittorrent is an auction: analyzing and improving bittorrent's incentives
Incentives play a crucial role in BitTorrent, motivating users to upload to others to achieve fast download times for all peers. Though long believed to be robust to strategic manipulation, recent work has empirically shown that BitTorrent does not ...
Comments