Distributed Systems Final project guidelines

The final lab assignment for the class is to undertake a mini research project of your choice in a group of 2-4 people. (Solo projects are possible with permission of the instructor.)

Your project should be guided by the following deadlines:

• By Monday, April 11 you must form a project team of 1-4 people and email the course staff to let us know with whom you will be working.

• Before Monday, April 18 you should schedule a meeting of your team with the course staff to discuss your proposed project. Once your proposal has been approved, send the course staff a short (1 paragraph) description of what you want to do, which may be posted on the web site so everybody knows what the different projects are.

  Please schedule your meeting sooner rather than later, in case your team needs to iterate on the proposal. Note, in particular, that it’s fine to meet with us if you don’t have a concrete plan yet, as we can suggest some things for you to look into.

  Note: If you want to combine your project with your research or with work for another class, this is in general fine, but please let us know at the time of the proposal. Make sure any other instructor or research supervisor involved knows that you plan to do this.

• Friday, May 27 you must email the course staff a final title and list of project team members, with email subject “final project title”, including a link to the git repository for your source code and a one paragraph abstract of your project (which can be the same as your proposal, but things may have changed).

• By Friday, June 3 you must send the course staff an email with subject “final project submission” containing a paper describing and evaluating your project that is no more than 6 pages in at least 11-point font. Papers and git repositories will be published on the class web site.

• Tuesday June 7 you will present your project to the class and demo what you have done in a mini one-day conference. The conference will include our registrar-assigned exam time (12:30pm-3:30pm), but continue later. We can schedule around you if you can’t be there for the whole afternoon. We will serve dinner.

You can use whatever programming language you and your partners want for the project. Two good choices are C++ and go. You may want to use Stanford’s shared computing cluster. Registring for the class should automatically bump your disk quota by 1 GB. You are also free to use cloud services.

Here are some ideas you might be interested in for projects. This list is by no means exhaustive.

• Build better tools for remote collaboration (text, voice, or video chat).
• Build a network object system for C++.
• Build something like Porcupine that addresses some of the paper’s shortcomings.
• Distributed protocols such as 2PC and Paxos are (1) short, (2) really hard to get right because of failures and uncertainty. Build a simple system that takes an implementation of these protocols and systematically explores their behavior in the face of crashes and network partitioning. See here for an example of how to do this for file systems.
• Build a checking infrastructure than can plug into the many different RAFT implementations and find protocol errors. The nice trick you can use here is that you do not have to specify correctness: each of the protocols must do the same observable action given the same sequence of crashes, partitions, recoveries. You may want to look at what Kyle Kingsbury has done with Jepsen.
• Build a clean, simple implementation of view stamped replication based on the updated Liskov paper that can be dropped into distributed systems in a way analogous to RAFT.
• Raspberry/pi is a very popular embedded computing platform. Build a distributed system using r/pi nodes and some interesting cheap hardware. More ambitious: build a clean, simple “bare-metal” toolkit on r/pi that allows people to easily build such systems.
• Build a simple, automatic distributed-parallel make implementation. Most makefiles are broken with spurious dependencies (slow) and missing dependencies (incorrect). Fortunately you can infer true dependencies automatically: kick off an existing (broken) build, intercept every “open()” system call to see which other files a given file depends on (e.g., all the files it #includes). Build a lightweight distributed system that does parallel distributed builds using these dependencies.
• Build a large file store, like GFS, and possibly using RAID like Zebra.
• Build a scalable virtual disk like Petal. (Maybe built using the Intel Open Storage Toolkit).
• Build a simplified version of a synchronization service like Google’s Chubby.
• Build something like MogileFS but instead of having a centralized database, replicate the DB using Paxos.
• Build a scalable web cache using consistent hashing or CARP.
• Build a highly-available, replicated DNS server that uses Paxos to ensure consistency of updates.
• Build a parallel debugger (ideally using some modification of GDB) that allows you to debug distributed systems. It should follow execution across message send and receive (analogously to procedure call/return).
• Build a distributed profiler that allows you to observe where time really goes in a distributed system. You should use it to spot bottlenecks in at least one existing distributed system.
• Build a system-call or message-level interposition library that can be slipped underneath an existing networked server and transparently be used to replicate these services so that they can survive failure and network partitioning. (Something similar but more complicated that what you would build: parrot.)
• Build a similar message-level interposition library that can be slipped underneath existing networked services and add security (nonces, secure checksums, encryption, authentication). Relevant: VPNs.
• Build a file synchronization tool like tra.
• Design an implement a Byzantine-fault-tolerant version of Raft.
• Design and implement a Byzantine-fault-tolerant state machine replication system that uses witnesses to keep fewer than 3f + 1 copies of the state, even with 3f + 1 servers.
• Build a raftscope-like visualization tool for a different protocol.
• Formally model and verify a consensus protocol, e.g., using TLA⁺ or IVy.
• Build a mobile-phone based privacy-preserving contact-tracing system for tracking the spread of infectious disease.
• Build a replicated system that leverages CRTDs (conflict-free replicated data types) to achieve eventual state conversion.
• Build a blockchain-based key management server that is more secure than the current PGP key servers. Optionally provide increased privacy via a technique like CONIKS.
• Design an asynchronous RPC library or other infrastructure around C++20 coroutines, so as to hide stack ripping while allowing a high degree of concurrent I/O.
• Modify an open-source database to use a public blockchain as a two-phase commit coordinator, so that you can securely commit an atomic transaction across any two systems using your version of the database. See this paper for inspiration.
• Build a replicated database that handles transactions in batches (i.e. for a blockchain), but where transactions in a batch can be applied in parallel and in any order. To maintain replicability, this database needs a set of commutative transaction semantics to permit this database to perform useful work (for any definition of “useful”).