Article

It's on me! the benefit of altruism in BAR environment

Authors:

Edmund L. Wong,

Joshua B. Leners,

Lorenzo AlvisiAuthors Info & Claims

DISC'10: Proceedings of the 24th international conference on Distributed computing

Pages 406 - 420

Published: 13 September 2010 Publication History

Abstract

Cooperation, a necessity for any peer-to-peer (P2P) cooperative service, is often achieved by rewarding good behavior now with the promise of future benefits. However, in most cases, interactions with a particular peer or the service itself eventually end, resulting in some last exchange in which departing participants have no incentive to contribute. Without cooperation in the last round, cooperation in any prior round may be unachievable. In this paper, we propose leveraging altruistic participants that simply follow the protocol as given. We show that altruism is a simple, necessary, and sufficient way to incentivize cooperation in a realistic model of a cooperative service's last exchange, in which participants may be Byzantine, altruistic, or rational and network loss is explicitly considered. By focusing on network-level incentives in the last exchange, we believe our approach can be used as the cornerstone for incentivizing cooperation in any cooperative service.

References

[1]

Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: PODC '06, pp. 53-62 (July 2006).

Digital Library

[2]

Adar, E., Huberman, B.A.: Free riding on Gnutella. First Monday 5(10), 2-13 (2000), http://www.firstmonday.org/issues/issue5_10/adar/index.html

[3]

Aiyer, A.S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.P., Porth, C.: BAR fault tolerance for cooperative services. In: SOSP '05, pp. 45-58 (October 2005).

Digital Library

[4]

Cohen, B.: Incentives build robustness in BitTorrent. In: First Workshop on the Economics of Peer-to-Peer Systems (June 2003).

[5]

Cripps, M.W., Mailath, G.J., Samuelson, L.: Imperfect monitoring and impermanent reputations. Econometrica 72(2), 407-432 (2004).

[6]

Cripps, M.W., Mailath, G.J., Samuelson, L.: Disappearing private reputations in long-run relationships. J. of Economic Theory 127(1), 287-316 (2007).

[7]

Eliaz, K.: Fault tolerant implementation. Rev. of Econ. Studies 69, 589-610 (2002).

[8]

Fudenberg, D., Levine, D.K.: Maintaining a reputation when strategies are imperfectly observed. Review of Economic Studies 59(3), 561-579 (1992).

[9]

Haeberlen, A., Kouznetsov, P., Druschel, P.: PeerReview: Practical accountability for distributed systems. In: SOSP '07, pp. 175-188 (October 2007).

Digital Library

[10]

Halpern, J., Teague, V.: Rational secret sharing and multiparty computation. In: Proc. 36th STOC, pp. 623-632 (2004).

Digital Library

[11]

Kremer, S., Markowitch, O., Zhou, J.: An intensive survey of non-repudiation protocols. Computer Communications 25(17), 1606-1621 (2002).

Digital Library

[12]

Kreps, D., Milgrom, P., Roberts, J., Wilson, R.: Rational cooperation in the finitely repeated prisoners' dilemma. J. of Economic Theory 27(2), 245-252 (1982).

[13]

Levin, D., LaCurts, K., Spring, N., Bhattacharjee, B.: BitTorrent is an auction: analyzing and improving BitTorrent's incentives. SIGCOMM Comput. Commun. Rev. 38(4), 243-254 (2008).

Digital Library

[14]

Levin, D., Sherwood, R., Bhattacharjee, B.: Fair file swarming with FOX. In: IPTPS '06 (February 2006).

[15]

Li, H., Clement, A., Marchetti, M., Kapritsos, M., Robinson, L., Alvisi, L., Dahlin, M.: FlightPath: Obedience vs choice in cooperative services. In: OSDI '08. pp. 355-368 (December 2008).

Digital Library

[16]

Li, H.C., Clement, A., Wong, E., Napper, J., Roy, I., Alvisi, L., Dahlin, M.: BAR Gossip. In: OSDI '06, pp. 191-204 (November 2006).

Digital Library

[17]

Locher, T., Moor, P., Schmid, S., Wattenhofer, R.: Free riding in bittorrent is cheap. In: HotNets '06 (November 2006).

[18]

Martin, J.P.: Leveraging altruism in cooperative services. Tech. Rep. MSR-TR- 2007-76, Microsoft Research (June 2007).

[19]

Pagnia, H., Gärtner, F.C.: On the impossibility of fair exchange without a trusted third party. Tech. Rep. TUD-BS-1999-02, Darmstadt University of Technology, Department of Computer Science, Darmstadt, Germany (March 1999).

[20]

Peterson, R.S., Sirer, E.G.: Antfarm: efficient content distribution with managed swarms. In: NSDI '09, pp. 107-122 (2009).

Digital Library

[21]

Piatek, M., Isdal, T., Anderson, T., Krishnamurthy, A., Venkataramani, A.: Do incentives build robustness in BitTorrent? In: NSDI '07, pp. 1-14 (April 2007).

Digital Library

[22]

Vassilakis, D.K., Vassalos, V.: An analysis of peer-to-peer networks with altruistic peers. Peer-to-Peer Networking and Applications 2(2), 109-127 (2009).

[23]

Wong, E.L., Leners, J.B., Alvisi, L.: It's on me! The benefit of altruism in BAR environments. Technical Report TR-10-08, UT Austin (2010).

Cited By

Vilaça XRodrigues LDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)On the Range of Equilibria Utilities of a Repeated Epidemic Dissemination Game with a MediatorProceedings of the 16th International Conference on Distributed Computing and Networking10.1145/2684464.2684482(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684482
Wong EAlvisi LFatourou PTaubenfeld G(2013)What's a little collusion between friends?Proceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484242(240-249)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484242
Alvisi LWong E(2013)Reasoning with MAD distributed systemsProceedings of the 24th international conference on Concurrency Theory10.1007/978-3-642-40184-8_1(1-4)Online publication date: 27-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40184-8_1
Show More Cited By

Recommendations

New P2P Sharing Incentive Mechanism Based on Social Network and Game Theory
WAINA '12: Proceedings of the 2012 26th International Conference on Advanced Information Networking and Applications Workshops

P2P technology has been used widely in file and live media streaming sharing fields. But the architecture of P2P technology which we used is imperfect. In P2P system, most users are free-rider. They were not sharing their own resource because the ...
Stackelberg thresholds in network routing games or the value of altruism
EC '07: Proceedings of the 8th ACM conference on Electronic commerce

Noncooperative network routing games are a natural model of userstrying to selfishly route flow through a network in order to minimize their own delays. It is well known that the solution resulting from this selfish routing (called the Nash equilibrium) ...
An Efficient Hybrid Peer-to-Peer System for Distributed Data Sharing

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer-to-peer networks in which peers are connected ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DISC'10: Proceedings of the 24th international conference on Distributed computing

September 2010

532 pages

ISBN:3642157629

Editors:
Nancy A. Lynch
Massachusetts Institute of Technology, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA
,
Alexander A. Shvartsman
University of Connecticut, Computer Science and Engineering, Storrs, CT

Sponsors

VEROMODO, Inc.
Booth Engineering Center for Advanced Technology at UCONN
University of Puerto Rico Rio Piedras

In-Cooperation

EATCS: European Association for Theoretical Computer Science

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 13 September 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vilaça XRodrigues LDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)On the Range of Equilibria Utilities of a Repeated Epidemic Dissemination Game with a MediatorProceedings of the 16th International Conference on Distributed Computing and Networking10.1145/2684464.2684482(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684482
Wong EAlvisi LFatourou PTaubenfeld G(2013)What's a little collusion between friends?Proceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484242(240-249)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484242
Alvisi LWong E(2013)Reasoning with MAD distributed systemsProceedings of the 24th international conference on Concurrency Theory10.1007/978-3-642-40184-8_1(1-4)Online publication date: 27-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40184-8_1
Vilaça XLeitão JRodrigues LBaldoni RShvarstman A(2011)N-party BAR TransferProceedings of the 3rd International Workshop on Theoretical Aspects of Dynamic Distributed Systems10.1145/2034640.2034647(18-22)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034640.2034647
Abraham IAlvisi LHalpern J(2011)Distributed computing meets game theoryACM SIGACT News10.1145/1998037.199805542:2(69-76)Online publication date: 10-Jun-2011
https://dl.acm.org/doi/10.1145/1998037.1998055
Wong ELevy IAlvisi LClement ADahlin M(2011)Regret freedom isn't freeProceedings of the 15th international conference on Principles of Distributed Systems10.1007/978-3-642-25873-2_7(80-95)Online publication date: 13-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25873-2_7
Vila$#231;a XLeitão JCorreia MRodrigues L(2011)N-party BAR transferProceedings of the 15th international conference on Principles of Distributed Systems10.1007/978-3-642-25873-2_27(392-408)Online publication date: 13-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25873-2_27

View Options

View options

Figures

Tables

Media

View Table of Conten