CS505 : Distributed Systems

Project Suggestions

Note: this list is neither comprehensive nor instructive. Some projects on this list may be beyond some students. Many of them probably cannot be implemented in their entirety before the course project ends. The goal is to find an interesting paper, and implement enough of it to get an understanding of how it work, and possibly make enhancements and improvements to it.

• NSDI 2010: Contracts (applied to generic multicast)

  Contracts: Practical Contribution Incentives for P2P Live Streaming
  Michael Piatek and Arvind Krishnamurthy, University of Washington; Arun
  Venkataramani, University of Massachusetts; Richard Yang, Yale University;
  David Zhang, PPLive
  

• NSDI 2007: BitTyrant

  Do Incentives Build Robustness in BitTorrent?
  Michael Piatek, Tomas Isdal, Thomas Anderson, and Arvind Krishnamurthy,
  University of Washington; Arun Venkataramani, University of Massachusetts
  Amherst
  

• NSDI 2010: Whanaungatanga

  Whanaungatanga: A Sybil-proof Distributed Hash Table
  Chris Lesniewski-Laas and M. Frans Kaashoek, MIT CSAIL
  

• NSDI 2009: Sybil-resilient voting

  Sybil-Resilient Online Content Voting
  Nguyen Tran, Bonan Min, Jinyang Li, and Lakshminarayanan Subramanian, New York
  University
  

• NSDI 2009: Application of Hypthetical TrInc to BitTorrent, Vivaldi, etc.

  TrInc: Small Trusted Hardware for Large Distributed Systems
  Dave Levin, University of Maryland; John R. Douceur, Jacob R. Lorch, and Thomas
  Moscibroda, Microsoft Research
  

• SOSP 2001: Resilient Overlay Networks

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

• NSDI 2004: Beehive: O(1) DHT

  Beehive: O(1) Lookup Performance for Power-Law Query Distributions in
  Peer-to-Peer Overlays
  Venugopalan Ramasubramanian and Emin Gün Sirer, Cornell University 
  

• SIGCOMM 2001: Content-Addressable Network

  A Scalable Content-Addressable Network
  Sylvia Ratnasamy (University of California at Berkeley and ACIRI), Paul Francis
  (Tahoe Networks), Mark Handley (ACIRI), Richard Karp (U.C. Berkeley and ACIRI),
  Scott Shenker (ACIRI) 
  

• USITS 2003: SkipNet

  SkipNet: A Scalable Overlay Network with Practical Locality Properties
  Nicholas J. A. Harvey, Microsoft Research and University of Washington; Michael
  B. Jones, Microsoft Research; Stefan Saroiu, University of Washington; Marvin
  Theimer and Alec Wolman, Microsoft Research 
  

• USENIX SEC 2004: Tor

  Tor: The Second-Generation Onion Router
  Roger Dingledine and Nick Mathewson, The Free Haven Project; Paul Syverson,
  Naval Research Lab 
  

• NSDI 2004: Coral

  Democratizing Content Publication with Coral
  Michael Freedman, Eric Freudenthal, and David Mazières, New York University 
  

• SOSP 2003: Samsara

  Samsara: Honor Among Thieves in Peer-to-Peer Storage
  Landon P. Cox, Brian D. Noble (University of Michigan)
  

[Overlay Network / DHT]

NSDI 2005 - Bandwidth-efficient Management of DHT Routing Tables
Jinyang Li, Jeremy Stribling, Robert Morris, and M. Frans Kaashoek, MIT
Computer Science and Artificial Intelligence Laboratory 

NSDI 2008 - UsenetDHT: A Low-Overhead Design for Usenet
Emil Sit, Robert Morris, and M. Frans Kaashoek, MIT CSAIL 

IPTPS 2002: Kademlia: A Peer-to-peer Information System Based on the XOR Metric
http://portal.acm.org/citation.cfm?id=687801

[Distributed FS / Storage / CDN]

NSDI 2009 - Flexible, Wide-Area Storage for Distributed Systems with WheelFS
Jeremy Stribling, MIT CSAIL; Yair Sovran, New York University; Irene Zhang and
Xavid Pretzer, MIT CSAIL; Jinyang Li, New York University; M. Frans Kaashoek
and Robert Morris, MIT CSAIL

NSDI 2008 - One Hop Reputations for Peer to Peer File Sharing Workloads
Michael Piatek, Tomas Isdal, Arvind Krishnamurthy, and Thomas Anderson,
University of Washington 

NSDI 2007 - Exploiting Similarity for Multi-Source Downloads Using File
Handprints
Himabindu Pucha, Purdue University; David G. Andersen, Carnegie Mellon
University; Michael Kaminsky, Intel Research Pittsburgh 

NSDI 2006 - Pastwatch: A Distributed Version Control System
Alexander Yip, Benjie Chen, and Robert Morris, MIT Computer Science and AI
Laboratory

NSDI 2004 - Explicit Control in the Batch-Aware Distributed File System
John Bent, Douglas Thain, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau,
and Miron Livny, University of Wisconsin, Madison 

OSDI 2006 - Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach,
Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, Google, Inc.

SOSP 2007 - Sinfonia: A New Paradigm for Building Scalable Distributed Systems
(Awarded a best paper award)
Marcos K. Aguilera (HP Labs), Arif Merchant (HP Labs), Mehul Shah (HP Labs),
Alistair Veitch (HP Labs), and Christos Karamanolis (VMWare)

SOSP 2007 - Dynamo: Amazon's Highly Available Key-Value Store (Awarded an
Audience Choice award)
Guiseppe DeCandia (Amazon.com), Deniz Hastorun (Amazon.com), Madan Jampani
(Amazon.com), Gunavardhan Kakulapati (Amazon.com), Avinash Lakshman
(Amazon.com), Alex Pilchin (Amazon.com), Swami Sivasubramanian (Amazon.com),
Peter Vosshall (Amazon.com), and Werner Vogels (Amazon.com)

OSDI 2006 - Ceph: A Scalable, High-Performance Distributed File System
Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos
Maltzahn, University of California, Santa Cruz

OSDI 2006 - Distributed Directory Service in the Farsite File System
John R. Douceur and Jon Howell, Microsoft Research

FAST 2008 - TierStore: A Distributed Filesystem for Challenged Networks in
Developing Regions
Michael Demmer, Bowei Du, and Eric Brewer, University of California, Berkeley

[Replication / Availability]

NSDI 2006 - Efficient Replica Maintenance for Distributed Storage Systems
Byung-Gon Chun, University of California, Berkeley; Frank Dabek, MIT Computer
Science and Artificial Intelligence Laboratory; Andreas Haeberlen, Rice
University/MPI-SWS; Emil Sit, MIT Computer Science and Artificial Intelligence
Laboratory; Hakim Weatherspoon, University of California, Berkeley; M. Frans
Kaashoek, MIT Computer Science and Artificial Intelligence Laboratory; John
Kubiatowicz, University of California, Berkeley; Robert Morris, MIT Computer
Science and Artificial Intelligence Laboratory

NSDI 2006 - PRACTI Replication Nalini Belaramani, Mike Dahlin, Lei Gao, Amol
Nayate, Arun Venkataramani, Praveen Yalagandula, and Jiandan Zheng, University
of Texas at Austin

NSDI 2006 - Exploiting Availability Prediction in Distributed Systems James W.
Mickens and Brian D. Noble, University of Michigan

NSDI 2005 - Shark: Scaling File Servers via Cooperative Caching Siddhartha
Annapureddy, Michael J. Freedman, and David Mazieres, New York University

NSDI 2005 - Glacier: Highly Durable, Decentralized Storage Despite Massive
Correlated Failures Andreas Haeberlen, Alan Mislove, and Peter Druschel, Rice
University 

SOSP 2003 - Preserving Peer Replicas By Rate-Limited Sampled Voting Petros
Maniatis, Mema Roussopoulos, TJ Giuli, David S. H. Rosenthal, Mary Baker, Yanto
Muliadi (Stanford University)

FAST 2009 - Smoke and Mirrors: Reflecting Files at a Geographically Remote
Location Without Loss of Performance Hakim Weatherspoon, Lakshmi Ganesh, and
Tudor Marian, Cornell University; Mahesh Balakrishnan, Microsoft Research,
Silicon Valley; Ken Birman, Cornell University

FAST 2009 - Cumulus: Filesystem Backup to the Cloud Michael Vrable, Stefan
Savage, and Geoffrey M. Voelker, University of California, San Diego

[Multicast/Anycast]

NSDI 2007 - Ricochet: Lateral Error Correction for Time-Critical Multicast
Mahesh Balakrishnan and Ken Birman, Cornell University; Amar Phanishayee,
Carnegie Mellon University; Stefan Pleisch, Cornell University

NSDI 2006 - OASIS: Anycast for Any Service Michael J. Freedman, New York
University and Stanford University; Karthik Lakshminarayanan, University of
California, Berkeley; David Mazières, Stanford University

SOSP 2003 - Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh
Dejan Kostic, Adolfo Rodriguez, Jeannie Albrecht, Amin Vahdat (Duke University)

[BFT/Consensus]

OSDI 2006 - The Chubby Lock Service for Loosely-Coupled Distributed Systems
Mike Burrows, Google Inc.

NSDI 2009 - Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults
Allen Clement, Edmund Wong, Lorenzo Alvisi, and Mike Dahlin, The University of
Texas at Austin; Mirco Marchetti, The University of Modena and Reggio Emilia

NSDI 2009 - Zeno: Eventually Consistent Byzantine-Fault Tolerance Atul Singh,
MPI-SWS and Rice University; Pedro Fonseca, MPI-SWS; Petr Kuznetsov, TU
Berlin/Deutsche Telekom Laboratories; Rodrigo Rodrigues, MPI-SWS; Petros
Maniatis, Intel Research Berkeley

NSDI 2007 - Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant Systems
Jinyuan Li, VMware, Inc.; David Mazières, Stanford University 

OSDI 2008 - Mencius: Building Efficient Replicated State Machines for WANs
Yanhua Mao, University of California, San Diego; Flavio P. Junqueira, Yahoo!
Research Barcelona; Keith Marzullo, University of California, San Diego 

OSDI 2006 - HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault
Tolerance James Cowling, Daniel Myers, and Barbara Liskov, MIT CSAIL; Rodrigo
Rodrigues, INESC-ID and Instituto Superior Técnico; Liuba Shrira, Brandeis
University 

SOSP 2005 - BAR Fault Tolerance for Cooperative Services. Amitanand S. Aiyer,
Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl
Porth (U.T. Austin)  

OSDI 2006 - BAR Gossip Harry C. Li, Allen Clement, Edmund L. Wong, Jeff Napper,
Indrajit Roy, Lorenzo Alvisi, and Michael Dahlin, The University of Texas at
Austin 

SOSP 2005 - Fault-scalable Byzantine Fault-Tolerant Services. Michael
Abd-El-Malek, Greg Ganger, Garth Goodson, Mike Reiter, Jay Wylie (CMU)

OSDI 2004 - FUSE: Lightweight Guaranteed Distributed Failure Notification John
Dunagan, Microsoft Research; Nicholas J. A. Harvey, Massachusetts Institute of
Technology; Michael B. Jones, Microsoft Research; Dejan Kostic, Duke
University; Marvin Theimer and Alec Wolman, Microsoft Research 

SOSP 2009 - UpRight Cluster Services Allen Clement (UT Austin), Manos Kapritsos
(UT Austin), Sangmin Lee (UT Austin), Yang Wang (UT Austin), Lorenzo Alvisi (UT
Austin), Mike Dahlin (UT Austin), Taylor Riché (UT Austin) 

[Speculation]

NSDI 2009 - Tolerating Latency in Replicated State Machines Through Client
Speculation Benjamin Wester, University of Michigan; James Cowling, MIT CSAIL;
Edmund B. Nightingale, Microsoft Research; Peter M. Chen and Jason Flinn,
University of Michigan; Barbara Liskov, MIT CSAIL

SOSP 2007 - Zyzzyva: Speculative Byzantine Fault Tolerance (Awarded a best
paper award.) Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement,
and Edmund Wong (UT Austin)

[Anonymity]

NSDI 2007 - Information Slicing: Anonymity Using Unreliable Overlays
Sachin Katti, Jeff Cohen, and Dina Katabi, Massachusetts Institute of Technology 

NSDI 2005 - Cashmere: Resilient Anonymous Routing
Li Zhuang and Feng Zhou, University of California, Berkeley; Ben Y. Zhao,
University of California, Santa Barbara; Antony Rowstron, Microsoft Research,
UK 

[Distributed Computation]

OSDI 2004 - MapReduce: Simplified Data Processing on Large Clusters
Jeffrey Dean and Sanjay Ghemawat, Google, Inc.