skip to main content
10.1145/1329125.1329187acmotherconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

An incentive mechanism for message relaying in unstructured peer-to-peer systems

Published: 14 May 2007 Publication History

Abstract

Distributed message relaying is an important function of a peer-to-peer system to discover service providers. Existing search protocols in unstructured peer-to-peer systems either create huge burden on communications or cause long response time. Moreover, these systems are also vulnerable to the free riding problem. In this paper we present an incentive mechanism that not only mitigates the free riding problem, but also achieves good system efficiency in message relaying for peer discovery. In this mechanism promised rewards are passed along the message propagation process. A peer is rewarded if a service provider is found via a relaying path that includes this peer. We provide some analytic insights to the symmetric Nash equilibrium strategies of this game, and an approximate approach to calculate this equilibrium. Experiments show that this incentive mechanism brings a system utility generally higher than breadth-first search and random walks, based on both the estimated utility from our approximate equilibrium and the utility generated from learning in the incentive mechanism.

References

[1]
Lada Adamic, Rajan Lukose, Amit Puniyani, and Bernardo Huberman. Search in power-law networks. Physical Review E, 64:046135, 2001.
[2]
Eytan Adar and Bernardo Huberman. Free riding on gnutella. First Monday, 5(10), 2000.
[3]
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2005.
[4]
Levente Buttyán and Jean-Pierre Hubaux. Stimulating cooperation in self-organizing mobile ad hoc networks. Technical Report NO. DSC/2001/046, Swiss Federal Institute of Technology, 2001.
[5]
Sam Chandan and Christiaan Hogendorn. the bucket brigade: Pricing and network externalities in peer-to-peer communications networks. In Telecommunications Policy Research Conference, 2001.
[6]
Nicolas Christin and John Chuang. A cost-based analysis of overlay routing geometries. In Proceedings of IEEE INFOCOM'05, 2005.
[7]
A. Crespo and H. Garcia-Molina. Routing indices for peer-to-peer systems. In Proceedings of the 28th Conference on Distributed Computing Systems (ICDCS), July 2002.
[8]
Michal Feldman, Kevin Lai, John Chuang, and Ion Stoica. Quantify disincentives in peer-to-peer networks. In Workshop on Economics of Peer-toPeer Systems, 2003.
[9]
Daniel Figueiredo, Jonathan Shapiro, and Don Towsley. Incentives to promote availability in peer-to-peer anonymity systems. In Proceedings of IEEE ICNP, 2005.
[10]
Philippe Golle, Kevin Leyton-Brown, Ilya Mironov, and Mark Lillibridge. Incentives for sharing in peer-to-peer networks. In Proceedings of the Second International Workshop on Electronic Commerce, 2001.
[11]
Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker. Search and replication in unstructured peer-to-peer networks. In ICS, New York, 2002.
[12]
Richard T. B. Ma, Sam C. M. Lee, John C. S. Lui, and David K. Y. Yau. An incentive mechanism for P2P networks. In ICDCS, Tokyo, Japan, 2004.
[13]
S. Micali and R. Rivest. Micropayments revisted. In Proceedings of CTRSA, 2002.
[14]
Chaki Ng, David Parkes, and Margo Seltzer. Strategyproof computing: Systems infrastructures for self-interested parties. In The First Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, June 2003.
[15]
C. H. Papadimitriou. Algorithms, games, and the internet. In Annual ACM Symposium on Theory of Computing (STOC), 2001.
[16]
Jeff Shneidman and David Parkes. Rationality and self-interest in peer-to-peer networks. In The Second International Workshop on Peer-to-Peer Systems (IPTPS'03), Berkeley, CA, February 2003.
[17]
Jeff Shneidman and David Parkes. Rationality and self-interest in peer-to-peer networks. In 2nd International Workshop on Peer-to-Peer Systems (IPTPS), 2003.
[18]
Jeff Shneidman, David Parkes, and Margo Seltzer. Overcoming rational manipulation in distributed mechanism implementations. Technical Report TR-12-03, Harvard University, 2003.
[19]
Dejan S. Milogicic, Vana Kalogeraki, Rajan Lukose, and etc. Peer-to-peer computing. Technical Report 2002-57RI, Hewlett-Packard Company, 2002.
[20]
Qixiang Sun and Hector Garcia-Molina. Slic: A selfish link-based incentive mechanism for unstructured peer-to-peer networks. In ICDCS, Tokyo, Japan, 2004.
[21]
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
[22]
Dimitrios Tsoumakos and Nick Roussopoulos. A comparison of peer-to-peer search methods. In International Workshop on the Web and Databases (WebDB), 2003.
[23]
D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393:440, 1998.
[24]
Beverly Yang and Hector Garcia-Molina. Improving search in peer-to-peer systems. In ICDCS, Vienna, Austria, 2002.
[25]
Beverly Yang and Hector Garcia-Molina. PPay: Micropayments for peer-to-peer systems. In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS), October 2003.
[26]
Bin Yu and Munindar P. Singh. Searching social networks. In Proceedings of Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 65--72, 2003.
[27]
S. Zhong, J. Chen, and Y. Yang. Sprite: a simple, cheat-proof, credit-based system for model ad-hoc netowrks. In Proceedings of INFOCOM, 2003.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems
May 2007
1585 pages
ISBN:9788190426275
DOI:10.1145/1329125
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]

Sponsors

  • IFAAMAS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 May 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. incentive mechanism
  2. message relaying
  3. peer-to-peer systems

Qualifiers

  • Research-article

Funding Sources

Conference

AAMAS07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)ReferencesIllegal Online File Sharing, Decision-Analysis, and the Pricing of Digital Goods10.1201/9781315383149-16(239-280)Online publication date: Nov-2016
  • (2015)Impacts of selfish behaviors on the scalability of hybrid clientIEEE/ACM Transactions on Networking10.1109/TNET.2014.234703523:6(1818-1831)Online publication date: 1-Dec-2015
  • (2013)Participation Incentives in BGPInternet Naming and Discovery10.1007/978-1-4471-4552-3_8(105-129)Online publication date: 2013
  • (2013)On the Economics of Identifier-Based DiscoveryInternet Naming and Discovery10.1007/978-1-4471-4552-3_7(91-103)Online publication date: 2013
  • (2010)Incentive strategy based on trust model in P2P networkProceedings of the 2nd international Asia conference on Informatics in control, automation and robotics - Volume 310.5555/1843971.1844018(192-195)Online publication date: 6-Mar-2010
  • (2010)Threshold behavior of incentives in social networksProceedings of the 19th ACM international conference on Information and knowledge management10.1145/1871437.1871647(1461-1464)Online publication date: 26-Oct-2010
  • (2010)Incentive strategy based on trust model in P2P network2010 2nd International Asia Conference on Informatics in Control, Automation and Robotics (CAR 2010)10.1109/CAR.2010.5456662(192-195)Online publication date: Mar-2010
  • (2009)FRAMEProceedings of the 2009 IEEE international conference on Communications10.5555/1817770.1818136(4638-4643)Online publication date: 14-Jun-2009
  • (2009)FRAME: An Innovative Incentive Scheme in Vehicular Networks2009 IEEE International Conference on Communications10.1109/ICC.2009.5199041(1-6)Online publication date: Jun-2009
  • (2009)A Fluid Background Traffic Model2009 IEEE International Conference on Communications10.1109/ICC.2009.5198605(1-6)Online publication date: Jun-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media