More Web Proxy on the site http://driver.im/

research-article

DCast: sustaining collaboration in overlay multicast despite rational collusion

Authors:

Phillip B. Gibbons,

Chenwei ShiAuthors Info & Claims

CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

Pages 567 - 580

https://doi.org/10.1145/2382196.2382256

Published: 16 October 2012 Publication History

Abstract

A key challenge in large-scale collaborative distributed systems is to properly incentivize the rational/selfish users so that they will properly collaborate. Within such a context, this paper focuses on designing incentive mechanisms for overlay multicast systems. A key limitation shared by existing proposals on the problem is that they are no longer able to provide proper incentives and thus will collapse when rational users collude or launch sybil attacks.

This work explicitly aims to properly sustain collaboration despite collusion and sybil attacks by rational users. To this end, we propose a new decentralized DCast multicast protocol that uses a novel mechanism with debt-links and circulating debts. We formally prove that the protocol offers a novel concept of safety-net guarantee: A user running the protocol will always obtain a reasonably good utility despite the deviation of any number of rational users that potentially collude or launch sybil attacks. Our prototyping as well as simulation demonstrates the feasibility and safety-net guarantee of our design in practice.

References

[1]

E. Adar and B. Huberman. Free riding on Gnutella. First Monday, 5(10), 2000.

[2]

C. Aperjis, M. Freedman, and R. Johari. Peer-assisted content distribution with prices. In CoNext, 2008.

Digital Library

[3]

L. P. Cox and B. D. Noble. Samsara: Honor among thieves in peer-to-peer storage. In SOSP, 2003.

Digital Library

[4]

J. Douceur. The Sybil attack. In IPTPS, 2002.

Digital Library

[5]

J. Feigenbaum and S. Shenker. Distributed algorithmic mechanism design: Recent results and future directions. In DIALM, 2002.

Digital Library

[6]

Y. Fu, J. Chase, B. Chun, S. Schwab, and A. Vahdat. SHARP: An architecture for secure resource peering. In SOSP, 2003.

Digital Library

[7]

K. Gummadi, S. Saroiu, and S. Gribble. King: Estimating latency between arbitrary internet end hosts. In SIGCOMM, 2002.

Digital Library

[8]

A. Hayrapetyan, E. Tardos, and T. Wexler. The effect of collusion in congestion games. In STOC, 2006.

Digital Library

[9]

I. Keidar, R. Melamed, and A. Orda. EquiCast: Scalable multicast with selfish users. In PODC, 2006.

Digital Library

[10]

S. Kremer, O. Markowitch, and J. Zhou. An Intensive Survey of Fair Non-Repudiation Protocols. Computer Comm., 25(17), 2002.

Digital Library

[11]

R. Landa, D. Griffin, R. Clegg, E. Mykoniati, and M. Rio. A sybilproof indirect reciprocity mechanism for peer-to-peer networks. In INFOCOM, 2009.

[12]

D. Levin, K. LaCurts, N. Spring, and B. Bhattacharjee. BitTorrent is an Auction: Analyzing and Improving BitTorrent's Incentives. In SIGCOMM, 2008.

Digital Library

[13]

D. Levin, R. Sherwood, and B. Bhattacharjee. Fair File Swarming with FOX. In IPTPS, 2006.

[14]

H. C. Li, A. Clement, M. Marchetti, M. Kapritsos, L. Robison, L. Alvisi, and M. Dahlin. Flightpath: Obedience vs. choice in cooperative services. In OSDI, 2008.

Digital Library

[15]

H. C. Li, A. Clement, E. L. Wong, J. Napper, I. Roy, L. Alvisi, and M. Dahlin. BAR Gossip. In OSDI, 2006.

Digital Library

[16]

G. J. Mailath and L. Samuelson. Repeated Games and Reputations. Oxford University Press, 2006.

[17]

A. Nandi, T.-W. J. Ngan, A. Singh, P. Druschel, and D. S. Wallach. Scrivener: Providing incentives in cooperative content distribution systems. In Middleware, 2005.

Digital Library

[18]

T.-W. J. Ngan, D. S. Wallach, and P. Druschel. Incentives-compatible peer-to-peer multicast. In P2P Econ, 2004.

[19]

N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.

Digital Library

[20]

M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in BitTorrent. In NSDI, 2007.

Digital Library

[21]

M. Piatek, T. Isdal, A. Krishnamurthy, and T. Anderson. One hop reputations for peer to peer file sharing workloads. In NSDI, 2008.

Digital Library

[22]

M. Piatek, A. Krishnamurthy, A. Venkataramani, R. Yang, and D. Zhang. Contracts: Practical Contribution Incentives for P2P Live Streaming. In NSDI, 2010.

Digital Library

[23]

M. Reiter, V. Sekar, C. Spensky, and Z. Zhang. Making peer-assisted content distribution robust to collusion using bandwidth puzzles. In ICISS, 2009.

Digital Library

[24]

S. Saroiu, P. Gummadi, and S. Gribble. Measuring and Analyzing the Characteristics of Napster and Gnutella Hosts. Multimedia Systems Journal, 9(2), 2003.

Digital Library

[25]

N. Tran, J. Li, and L. Subramanian. Collusion-resilient Credit-based Reputations for Peer-to-peer Content Distribution. In NetEcon, 2010.

Digital Library

[26]

V. Vishnumurthy, S. Chandrakumar, and E. G. Sirer. Karma: A secure economic framework for peer-to-peer resource sharing. In P2P Econ, 2003.

[27]

B. Yang and H. Garcia-Molina. PPay: Micropayments for peer-to-peer systems. In CCS, 2003.

Digital Library

[28]

H. Yu. Sybil defenses via social networks: A tutorial and survey. ACM SIGACT News, 42(3), 2011.

Digital Library

[29]

H. Yu, P. B. Gibbons, and C. Shi. Brief Announcement: Sustaining Collaboration in Multicast despite Rational Collusion. In PODC, 2011.

Digital Library

[30]

Z. Zhang, S. Chen, and M. Yoon. MARCH: A Distributed Incentive Scheme for Peer-to-Peer Networks. In INFOCOM, 2007.

Digital Library

Cited By

Troncoso CIsaakidis MDanezis GHalpin H(2017)Systematizing Decentralization and Privacy: Lessons from 15 Years of Research and DeploymentsProceedings on Privacy Enhancing Technologies10.1515/popets-2017-00562017:4(404-426)Online publication date: 10-Oct-2017
https://doi.org/10.1515/popets-2017-0056
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

Index Terms

DCast: sustaining collaboration in overlay multicast despite rational collusion
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Sustaining collaboration in multicast despite rational collusion
PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

This paper focuses on designing incentive mechanisms for overlay multicast systems. Existing proposals on the problem are no longer able to provide proper incentives when rational users collude or launch sybil attacks. To overcome this key limitation, ...
Mechanisms for multi-unit combinatorial auctions with a few distinct goods
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

We design and analyze deterministic truthful approximation mechanisms for multi-unit Combinatorial Auctions with only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of ...
Prior-free auctions with ordered bidders
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

Prior-free auctions are robust auctions that assume no distribution over bidders' valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security

October 2012

1088 pages

ISBN:9781450316514

DOI:10.1145/2382196

General Chair:
Ting Yu
North Carolina State University, USA
,
Program Chairs:
George Danezis
Microsoft Research Cambridge, UK
,
Virgil Gligor
Carnegie Mellon University, USA

Copyright © 2012 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]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'12

Sponsor:

SIGSAC

CCS'12: the ACM Conference on Computer and Communications Security

October 16 - 18, 2012

North Carolina, Raleigh, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Troncoso CIsaakidis MDanezis GHalpin H(2017)Systematizing Decentralization and Privacy: Lessons from 15 Years of Research and DeploymentsProceedings on Privacy Enhancing Technologies10.1515/popets-2017-00562017:4(404-426)Online publication date: 10-Oct-2017
https://doi.org/10.1515/popets-2017-0056
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

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents