CS6460 - Peer-to-Peer Systems

Spring 2010

Emin Gun Sirer

Course Info, Objective, Due Dates

Meeting Time: Tuesdays & Thursdays, 1:25-2:40pm, Upson 109.

Objective: To establish a foundation for the study of self-organizing systems, with particular emphasis on peer-to-peer systems.


0. January 26 Intro Introduction and course organization Gun
1. January 28 Distributed Data Structures Anthony Rowstron and Peter Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems. In Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), November 2001.

Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, Hari Balakrishnan. Chord: A Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the ACM SIGCOMM Conference, San Diego, CA, September 2001
2. February 02 Distributed Hash Tables Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. Proceedings of the 2001 conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2001.

Dahlia Malkhi, Mani Naor, and D. Ratajczak. Viceroy: A scalable and dynamic emulation of the butterfly. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2002.

Please describe the operation of Viceroy in a manner that is sufficiently clear and cogent that someone who is solely reading your description can implement the system. Then describe the advantages and disadvantages of CAN compared to Chord and Pastry.

3. February 04 Distributed Hash Tables Anjali Gupta, Barbara Liskov, and Rodrigo Rodrigues. One Hop Lookups for Peer-to-Peer Overlays. Ninth Workshop on Hot Topics in Operating Systems (HotOS-IX). Lihue, Hawaii, USA. May 2003.

Indranil Gupta, Ken Birman, Prakash Linga, Alan Demers, and Robbert van Renesse. Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems, 2003.

Discuss the impact of malicious participants on these two systems. Which of these systems is more resilient to Byzantine peers?

4. February 09 Secure Filesharing Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. In Proc. of the ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000.

Marc Waldman and David Mazieres. Tangler: A Censorship-Resistant Publishing System Based On Document Entanglements. In Proceedings of the 8th ACM Conference on Computer and Communications Security, pages 126-135, November 2001.

Summarize the key security mechanisms that Freenet uses to prohibit a user from occluding an object previously published by another user. Then describe the key entangling operation in Tangler, and discuss under what conditions such an entanglement system is necessary and useful.

5. February 11 Replication Qin Lv, Pei Cao, Edith Cohen, Kai Li, and Scott Shenker. Search and Replication in Unstructured Peer-to-Peer Networks. In Proceedings of the 16th annual ACM International Conference on Supercomputing, 2002.

Venugopalan Ramasubramanian and Emin Gun Sirer. Beehive: O(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays. In Proceedings of Networked System Design and Implementation, March 2004.

Briefly describe the operation of the two systems. You should, on your own, re-drive the equations shown in the paper to a point where, if called to the board with your notes, you can drive the same equations from scratch, though you do not need to submit your derivation.

6. February 16 Security John R. Douceur. The Sybil Attack. In Proceedings of the IPTPS02 Workshop, Cambridge, MA (USA), March 2002.

Atul Singh, Miguel Castro, Peter Druschel, and Antony Rowstron. Defending Against Eclipse Attacks on Overlay Networks. In Proceedings of the European SIGOPS Workshop, Leuven, Belgium, September 2004.

Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. .

Submit three paragraphs that describe the attacks presented in these papers as well as the proposed approaches to thwart them.

7. February 18 Approximate Queries F. Araujo, L. Rodrigues. GeoPeer: A Location-Aware Peer-to-Peer System. In Proceedings of the 3rd IEEE International Symposium on Network Computing and Applications (IEEE NCA04), pp. 39-46, August, 2004, Cambridge, MA, USA.

Adina Crainiceanu, Prakash Linga, Johannes Gehrke, Jayavel Shanmugasundaram. Querying Peer-to-Peer Networks Using P-Trees.

Ashwin R. Bharambe, Mukesh Agrawal, Srinivasan Seshan. Mercury: Supporting Scalable Multi-Attribute Range Queries.

Bernard Wong, Alex Slivkins, Emin Gun Sirer. Cubit.

Under what circumstances are range and approximate queries useful? Please go beyond the discussion given in the papers to discuss real systems one may want to build that need a range or approximate search primitive. Are the applications discussed by these systems sufficiently compelling?

8. February 23 Measurements Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. UW CS technical report.

Krishna P. Gummadi, Richard J. Dunn, Stefan Saroiu, Steven D. Gribble, Henry M. Levy, John Zahorjan. Measurement, Modeling, and Analysis of a Peer-to-Peer File-Sharing Workload. SOSP

If you were building a P2P application today, what precise data would you like to know, and how would you go about collecting such data given the types of resources currently available? In the first part of your write-up, assume omniscient observational power, and describe everything you might want to know. In the second part, describe how you would approach this ideal dataset given realistic tools.

Bo Peng
9. February 25 P2P Resource Exchange Landon P. Cox, Brian D. Noble. Samsara: Honor Among Thieves in Peer-to-Peer Storage SOSP 2003.

Yun Fu, Jeffery Chase, Brent Chun, Stephen Schwab, Amin Vahdat. SHARP: An Architecture for Secure Resource Peering SOSP 2003.

Beverly Yang, Hector Garcia-Molina. PPay: Micropayments for Peer-to-Peer Systems. In ACM CCS 2003.

Vivek Vishnumurthy, Sangeeth Chandrakumar and Emin Gun Sirer. KARMA: A Secure Economic Framework for P2P Resource Sharing. In Workshop on the Economics of Peer-to-Peer Systems, Berkeley, California, June 2003

Describe Samsara's operation. Given the amount of resource discrepancy between nodes, does a scheme like Samsara make sense? If not, what does? Briefly describe SHARP, PPay and Karma. Do virtual or micro-currencies make sense given that we could just use real money?

10. March 02 Nameservice Russ Cox, Athicha Muthitacharoen and Robert Morris. Serving DNS Using a Peer-to-Peer Lookup Service. IPTPS 2002.

Venugopalan Ramasubramanian and Emin Gun Sirer. The Design and Implementation of a Next Generation Name Service for the Internet. In Proceedings of the SIGCOMM Conference, Portland, Oregon, August 2004.

Compare the system described here to OpenDNS and/or Google DNS.

Matt Pearson
11. March 04 Backup Rawstron, Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. 18th SOSP.

Dabek, Kaashoek, Morris, Stoica. Wide-area cooperative storage with CFS. 18th SOSP

Is a DHT a suitable substrate for backup placement? Describe the requisite properties of a backup system, and argue for or against using a DHT.

Ki Suh
12. March 09 Routing David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris. Resilient Overlay Networks. Proc. 18th ACM SOSP, Banff, Canada, October 2001.

K. Gummadi, Madhyastha, Gribble, Levy, Wetherall. Improving the reliability of Internet paths with one-hop source routing. OSDI 2004

How would you improve the scalability of RONs?

13. March 11 Network Positioning T. S. Eugene Ng and Hui Zhang. Predicting Internet Network Distances with Coordinates-Based Approaches. INFOCOM, New York, NY, June 2002.

Frank Dabek, Russ Cox, Frans Kaahoek, Robert Morris. Vivaldi: A Decentralized Network Coordinate System. In Proceedings of SIGCOMM 2004, Portland, OR, Aug, 2004.

Bernard Wong, Alex Slivkins, Emin Gun Sirer. Meridian: A Lightweight Framework for Network Positioning without Virtual Coordinates. SIGCOMM 2005.

What kinds of position-related queries do you think are important for applications?

14. March 16 Anonymity Michael K. Reiter, Aviel D. Rubin. Crowds: Anonymity for Web Transactions.

Rob Sherwood, Bobby Bhattacharjee, Aravind Srinivasan. P5: A Protocol for Scalable Anonymous Communication. IEEE Symposium on Security and Privacy 2002.

David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. Journal of Cryptology, pp. 65-75, 1(1), 1988.

Emin Gun Sirer, Sharad Goel, Mark Robson, Dogan Engin. Eluding Carnivores: File Sharing with Strong Anonymity. In Proceedings of the European SIGOPS Workshop, Leuven, Belgium, September 2004.

Compare and contrast MIXes, DC-Nets and P5.

Taiyang Chen
15. March 18 Reputation Sepandar D. Kamvar, Mario T. Schlosser and Hector Garcia-Molina. The EigenTrust Algorithm for Reputation Management in P2P Networks. In WWW, 2003.

Sonja Buchegger and Jean-Yves Le Boudec. A Robust Reputation System for P2P and Mobile Ad-hoc Networks. In Workshop on Economics of Peer-to-Peer Systems, April 2004.

Kevin Walsh and Emin Gun Sirer. Experience with an Object Reputation System for Peer-to-Peer Filesharing. In Proceedings of Networked System Design and Implementation, San Jose, California, May 2006.

Compare and contrast an object reputation system against a reputation system for principals. What are the differences? What are the features both have in common?

March 23 Have a nice Spring Break
March 25
16. March 30 File Distribution and Multicast Bram Cohen. BitTorrent. P2PEcon 2003.

Dejan Kostic, Adolfo Rodriguez, Jeannie Albrecht, and Amin Vahdat Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh. SOSP 2003.

Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, Atul Singh. SplitStream: High-Bandwidth Multicast in Cooperative Environments.
17. April 01 File Distribution and Multicast Dongyu Qiu, R. Srikant. Modeling and Performance Analysis of Bit Torrent-Like Peer-to-Peer Networks. SIGCOMM 2004.

Ryan Peterson and Emin Gun Sirer. Antfarm. NSDI 2009.
18. April 06 File Distribution and Multicast John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek, and James W. O'Toole, Jr. Overcast: Reliable Multicasting with an Overlay Network. OSDI 2000 Michael Ryan
19. April 08 Publish-Subscribe M. Castro, P. Druschel, A-M. Kermarrec and A. Rowstron. SCRIBE: A large-scale and decentralised application-level multicast infrastructure. IEEE Journal on Selected Areas in Communication (JSAC), Vol. 20, No, 8, October 2002.

A. Carzaniga, D.S. Rosenblum, and A.L. Wolf. Design and Evaluation of a Wide-Area Event Notification Service. ACM Transactions on Computer Systems, 19(3):332-383, Aug 2001.
20. April 13 Coding John Byers, Michael Luby, Michael Mitzenmacher and A. Rege. A Digital Fountain Approach to Reliable Distribution of Bulk Data. In Proceedings of ACM SIGCOMM, Vancouver, Canada, September 1998.

John Byers, Michael Luby, and Michael Mitzenmacher. Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads. In Proceedings of INFOCOM, 1999.

Christos Gkantsidis, Pablo Rodriguez. Network Coding for Large Scale Content Distribution. IEEE/INFOCOM 2005, Miami. March 2005.
21. April 15 Specification Techniques Boon Thau Loo, Tyson Condie, Joseph M. Hellerstein, Petros Maniatis, Timothy Roscoe, Ion Stoica. Implementing Declarative Overlays. In Proceedings of ACM Symposium on Operating Systems Principles (SOSP), Brighton, UK, October 2005.

Adolfo Rodriguez, Charles Killian, Sooraj Bhat, Dejan Kostic, and Amin Vahdat. MACEDON: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks. In Proceedings of the Symposium on Networked Systems Design and Implementation, March 2004.
22. April 20 GRID and P2P Ian Foster, Carl Kesselman, Jeffrey M. Nick, Steven Tuecke. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration.

Ian Foster, Adriana Iamnitchi. On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing. In Proceedings of the International Workshop on Peer-to-Peer Systems, Berkeley, CA, February 2003.
23. April 22 Cycle Sharing SETI@home. http://setiathome.berkeley.edu/.

Virginia Lo, Daniel Zappala, Dayi Zhou, Yuhong Liu, Shanyu Zhao. Cluster Computing on the Fly: P2P Scheduling of Idle Cycles in the Internet. In Proceedings of the International Workshop on Peer-to-Peer Systems, San Diego, CA, February 2004.
24. April 27 Skip
25. April 29 P2P and Social Networks Tomas Isdal, Michael Piatek, Arvind Krishnamurthy, Thomas Anderson. Privacy-preserving P2P data sharing with OneSwarm, Technical report, UW-CSE. 2009.

J.A. Pouwelse, P. Garbacki, J. Wang, A. Bakker1 , J. Yang, A. Iosup, D.H.J. Epema, M. Reinders, M. van Steen1 , H.J. Sips. Tribler: A social-based Peer-to-Peer system.
26. May 04 Skip
27. May 06 Legal Issues and P2P Fred von Lohmann. Peer-to-Peer File Sharing and Copyright Law: A Primer for Developers. In Proceedings of the International Workshop on Peer-to-Peer Systems, Berkeley, CA, February 2003.

John Moye. How SONY Survived: Peer-to-peer Software, Grokster, and Contributory Copyright Liability in the Twenty-First Century. 84 NC Law Review 646.

Additional Reading

28. May 11 DHTs Ben Zhao, John Kubiatowicz, Anthony Joseph. Tapestry: An Infrastructure for Wide-area Fault-tolerant Location and Routing. U. C. Berkeley Technical Report UCB/CSD-01-1141, April, 2001.

Petar Maymounkov and David Mazieres. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS02), March 2002.

Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal hash table. In Proceedings of IPTPS, Feb 2003