615 - Peer-to-Peer Systems

Spring 2006

Emin Gun Sirer

Course Info

Meeting Time: Tuesdays & Thursdays, 1:25-2:40pm
Meeting Room: 218 Olin Hall

Course Objective, Topics and Schedule

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


Homework 1 (due March 2nd, midnight)
Homework 2 (due April 28th, midnight)

Schedule

#DateTopicPaperPresenter
0. January 24 Intro Introduction and course organization

comments and discussion
Gun
1. January 26 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.

comments and discussion
Gun
2. January 31 Distributed Hash Tables 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

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.

Additional Reading:
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

comments and discussion
Gun
3. 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.

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

comments and discussion
Gun
4. February 07 Distributed Hash Tables 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).

comments and discussion
Gun
5. February 09 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.

comments and discussion
Tudor Marian
6. February 14 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.

comments and discussion
Ryan Peterson
7. February 16 Range 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.

comments and discussion
Nick Gerner
8. February 21 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. .

comments and discussion
Ari Rabkin and Andrew Cunningham
9. 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

comments and discussion
Kelvin So
10. February 28 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

comments and discussion
Ymir Vigfusson
11. 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.

comments and discussion
Shiang-Jia
12. March 07 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

comments and discussion
Victoria Krafft
13. 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 200

comments and discussion
Philip Kuryloski
14. March 14 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.

comments and discussion
Ivan Stoyanov
15. 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.

comments and discussion
Gun
March 21 Have a nice Spring Break
March 23
16. March 28 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.

comments and discussion
Gun
17. 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.

comments and discussion
Oliver Kennedy
18. April 04 File Distribution and Multicast Dongyu Qiu, R. Srikant. Modeling and Performance Analysis of Bit Torrent-Like Peer-to-Peer Networks. SIGCOMM 2004

comments and discussion
Ian Kash
19. 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

comments and discussion
Kevin Markman
20. April 11 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.

comments and discussion
Theo Chao
21. 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.

comments and discussion
Andrew Cunningham
22. April 18 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.

comments and discussion
Kelvin So
23. 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.

comments and discussion
Oliver Kennedy
24. April 25 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.

comments and discussion
Nick Gerner
25. April 27 Research Summaries Ryan Peterson. Corona. NSDI 2006.
Kelvin So. Optimal Failure Detection.
Ivan Stoyanov. Octant.
Andrew Cunningham and Ariel Rabkin. Anonymous Communication
Victoria Krafft. Live Multimedia Distribution.
Shiang-Jia.
Kevin Markman.
Theo Chao.
Oliver Kennedy.
Nick Gerner.

comments and discussion
Everyone
26. May 02 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.

comments and discussion
Niranjan Sivakumar
27. May 04 Final Course Wrap-up

comments and discussion
Gun