skip to main content
10.1145/2018436.2018458acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article
Free Access

Design space analysis for modeling incentives in distributed systems

Authors Info & Claims
Published:15 August 2011Publication History

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.

Skip Supplemental Material Section

Supplemental Material

sigcomm_6_1.mp4

References

  1. R. Axelrod. The Evolution of Cooperation. Basic Books, New York, 1984.Google ScholarGoogle Scholar
  2. A. Bharambe, C. Herley, and V. Padmanabhan. Analyzing and improving a BitTorrent network's performance mechanisms. In INFOCOM, 2006.Google ScholarGoogle Scholar
  3. C. Buragohain, D. Agrawal, and S. Suri. A game theoretic framework for incentives in P2P systems. In IEEE P2P, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. A.L.H. Chow, L. Golubchik, V. Misra. BitTorrent: An extensible heterogeneous model. In INFOCOM, 2009.Google ScholarGoogle Scholar
  5. R. Dash, N. Jennings, and D. Parkes. Computational-mechanism design: A call to arms. IEEE Intelligent Systems, 18:40--47, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. J. Feigenbaum and S. Shenker. Distributed Algorithmic Mechanism Design: Recent Results and Future Directions. In ACM DIALM, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. R. Hahnel and A. Library. The ABCs of political economy: A modern approach. Pluto Press, 2002.Google ScholarGoogle Scholar
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. D. Hruschka and J. Henrich. Friendship, cliquishness, and the emergence of cooperation. Journal of Theoretical Biology, 239:1--15, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  11. R. Izhak-Ratzin. Collaboration in BitTorrent systems. In IFIP-TC Networking, pp. 338--351, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. S. Jun and M. Ahamad. Incentives in BitTorrent induce free riding. In P2PECON, 2005.Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. A.-M. Kermarrec and M. van Steen, editors. ACM SIGOPS Operating Systems Review 41, Special Issue on Gossip-Based Networking. 2007.Google ScholarGoogle Scholar
  14. A. Legout, N. Liogkas, E. Kohler, and L. Zhang. Clustering and sharing incentives in bittorrent systems. In ACM SIGMETRICS, pp. 301--312, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. D. Levin, K. LaCurts, N. Spring, and B. Bhattacharjee. BitTorrent is an auction: analyzing and improving BitTorrent's incentives. In ACM SIGCOMM, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. T. Locher, P. Moor, S. Schmid, and R. Wattenhofer. Free riding in BitTorrent is cheap. In HotNets-V, 2006.Google ScholarGoogle Scholar
  18. R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Experiences applying game theory to system design. In ACM PINS, pp. 183--190, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. G. Mailath. Do people play Nash equilibrium? Lessons from evolutionary game theory. Journal of Economic Literature, 36:1347--1374, 1998.Google ScholarGoogle Scholar
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  21. 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 ScholarGoogle Scholar
  22. M. Osborne and A. Rubinstein. A course in game theory. The MIT press, 1994.Google ScholarGoogle Scholar
  23. F. Pianese, J. Keller, and E. Biersack. PULSE, a flexible P2P live streaming system. In INFOCOM, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  24. M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in BitTorrent. In NSDI, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. 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 ScholarGoogle ScholarCross RefCross Ref
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. A. Rao, A. Legout, and W. Dabbous. Can Realistic BitTorrent Experiments Be Performed on Clusters? In IEEE P2P, 2010.Google ScholarGoogle Scholar
  28. E. Rasmusen. Games and information: An introduction to game theory. Wiley-Blackwell, 2007.Google ScholarGoogle Scholar
  29. T. Roughgarden and É. Tardos. How bad is selfish routing. Journal of the ACM, 49:236--259, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. K. Rzadca, A. Datta, and S. Buchegger. Replica placement in p2p storage: Complexity and game theoretic analyses. In ICDCS, pp. 599--609, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  32. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Design space analysis for modeling incentives in distributed systems

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in
          • Published in

            cover image ACM Conferences
            SIGCOMM '11: Proceedings of the ACM SIGCOMM 2011 conference
            August 2011
            502 pages
            ISBN:9781450307970
            DOI:10.1145/2018436
            • cover image ACM SIGCOMM Computer Communication Review
              ACM SIGCOMM Computer Communication Review  Volume 41, Issue 4
              SIGCOMM '11
              August 2011
              480 pages
              ISSN:0146-4833
              DOI:10.1145/2043164
              Issue’s Table of Contents

            Copyright © 2011 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 15 August 2011

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article

            Acceptance Rates

            SIGCOMM '11 Paper Acceptance Rate32of223submissions,14%Overall Acceptance Rate554of3,547submissions,16%

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader