714 - Topics in Computer Systems - Peer-to-Peer and Overlay Networks

Spring 2005

Emin Gun Sirer

Course Info

Meeting Time: Mondays & Wednesdays, 10:10-11:30 am
Meeting Room: Systems Lab, Upson 331,

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.


Jan 26IntroIntroduction and course organizationGun
Jan26 Distributed Hash Tables Anthony Rowstron and Peter Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems. Gun
Jan 31Distributed Hash Tables Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, Hari Balakrishnan. Chord: A Peer-to-Peer Lookup Service for Internet Applications. ACM SIGCOMM Conf., San Diego, CA, September 2001

Ben Zhao, John Kubiatowicz, Anthony Joseph. Tapestry: An Infrastructure for Wide-area Fault-tolerant Location and Routing.
Feb 2Distributed Hash Tables 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. Gun
Feb 7Distributed 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 (IPTPS '03), 2003.
Feb 9Distributed Hash Tables Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal hash table. In Proceedings of IPTPS, Feb 2003. Kevin
Feb 14Distributed 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). Gun
Feb 16Admin Snowstorm and discussion of potential projects. Gun
Feb 21Distributed Hash Tables Krzystof Ostrowski and Emin Gun Sirer. MultiHash. Work in Progress. Gun
Feb 23Distributed Hash Tables Guest Lecture: Sean Rhea (Berkeley). OpenDHT. Sean Rhea (Berkeley)
Feb 28Geographic Distributed Hash Tables and Range Queries Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network.

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.
Mar 2Replication 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.
Yee Jiun
Mar 7Security 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
Mar 9Measurements 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.
Mar 14Nameservice 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.
Mar 16P2P 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.
Mar 18Backup 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.
Apr 4Routing 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
Apr 6Network Positioning T. S. Eugene Ng and Hui Zhang. Predicting Internet Network Distances with Coordinates-Based Approaches. INFOCOM'02, 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.. Cornell TR.
Apr 11Anonymity 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.
Apr 13Reputation 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.
Apr 18File 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.
Yee Jiun
Apr 26File Distribution and Multicast Dongyu Qiu, R. Srikant. Modeling and Performance Analysis of Bit Torrent-Like Peer-to-Peer Networks. SIGCOMM 2004. Gun
Apr 27File 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. Gun
May 5Publish-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.
May 6  Research Summaries and Course Wrap-up. Gun & Everyone