CSEP 590A: Distributed Systems
Assignments

Course Goal

The goal of this course is to help you understand and apply distributed systems concepts; the course assignments are designed with that in mind.

Reading and Blogs

You are expected to have read the assigned papers for the class before the class meeting; the material is complex enough that you will fall quickly behind if you are not prepared.

This quarter we will be doing things a bit differently than you are used to in other classes that read research papers. Instead of asking each of you to write a summary for each of a number of papers over the quarter, the class will write a collective review for the reading in this course.

How this works: by 5:30pm on the day of each class, please log onto the message board on the course web site (note you'll need your UW-ID login and password), read the prior posts for that week, and then add some useful comment to one of the threads for that week. Typically there will be one thread per paper and section of the book. The comments you post can/should be brief -- e.g., just a couple sentences -- that adds something to the ongoing discussion in that thread. Examples include: the main idea of the paper, a list of pro's, a list of con's, an example why you think the approach would/would not work, a flaw in the evaluation, a comparison to some alternate approach, a pointer to some followup work you found on the web, an application of the idea that's now in practice. My only suggestion is to try to avoid simple "me too" posts; we're not voting. "I agree with Tanya because..." or "I disagree with Tanya because..." are perfectly fine.

Prior to class, make sure to read the rest of the blog.

Your posts to the blog will be lightly graded. The main benefit is to help foster you learning from each other after reading the papers, you collectively will know this material better than I do, even if you don't realize that yet. Note: if you posted a comment for the first week's class, you may skip any single other week in other words, you only need to do nine blog postings.

Programming Assignments

Many of the concepts in the class have a great deal of subtlety; the best way to really understand them is implement them for yourself. We provide a selection of assignments, to give you some options to make sure that the projects are relevant to your work. Each of the assignments is based on the material for a given week; the assignment is due at the beginning of class no later than four weeks after the end of that class; however, all assignments are due no later than midnight, Wednesday June 7 (even if that is less than three weeks).

Since students sometimes like to work in groups and sometimes like to work alone, we have a sliding scale for workload: for a group of size k students, you are to do k+1 assignments over the course of the quarter. Since the assignments vary in difficulty, the course grading will take that into account (e.g., you can pass the course doing only the easy assignments, but to ace the course you'll need to try some of the harder ones). Most of the assignments can be either simulated (e.g., with UNIX or NT processes doing interprocess commmunication), or tested in a live setting such as PlanetLab or Emulab. PlanetLab/Emulab testing automatically increases the level of difficulty one notch. We can obtain PlanetLab and Emulab accounts for interested groups.

The turn in for the assignment should be a tar or zip file with commented source code, an executable and script/instructions for running it, and a several page writeup describing the solution, why it should work, why you believe it does work, etc. Note that most of the assignments involve very small amounts of code, but code that is difficult to get precisely correct.

You should use E-Submit to turn in your assignments. You will need your UWNetID to access the online form.

Email questions about the assignments are welcome, but they should be sent to both of us (Tom and Kate) so that we make sure to give consistent instructions to everyone.

The specific projects are:

Week 1:

(due 04/26/2006)

Build a fault tolerant web server front end. This should accept TCP/IP packets on one side, and forward them transparently to whichever back end machines are up, such that the client nodes do not need to know about the existence of the back end machines (e.g., by doing network address translation). The front end should be fault tolerant, in that if it fails, its peer can automatically take over its function without any disruption to the client machines.

Difficulty: moderate

Week 2:

(due 05/03/2006)

Implement a time synchronization protocol, and use it to coordinate a low rate DoS attack on your home machine from PlanetLab. Instead of having everyone send at a fixed rate, a low rate attack chirps a packet every half second. How many machines are needed before your home machine becomes unusable?

Difficulty: hard

Week 3:

(due 05/10/2006)

Implement causally ordered communication and show that it works (e.g., for predicate detection, or ordering simulated email, etc.).

Difficulty: easy

Week 4:

(due 06/07/2006)

Implement the Paxos consensus protocol.

Difficulty: hard

Week 5:

(due 05/24/2006)

Implement a sequentially consistent distributed cache coherence protocol. Does message ordering matter? How about causal ordering?

Difficulty: easy

Implement a two phase commit protocol.

Difficulty: moderate

Implement a three phase commit protocol.

Difficulty: hard

Week 6:

(due 06/07/2006)

Implement the Castro/Liskov Byzantine fault tolerance protocol.

Difficulty: hard

Week 7:

(due 06/07/2006)

Implement a cache coherence protocol with eventual consistency for disconnected operation.

Difficulty: moderate

Week 8:

(due 06/07/2006)

Implement the chord distributed hash table and show it works under high degrees of churn.

Difficulty: hard

Modify bit-torrent to work for streaming data, e.g., March Madness on Demand

Difficulty: hard

Week 9:

(due 06/07/2006)

Hack a kernel implementation of a client's TCP stack to spoof a web server into sending traffic at a gigabit a second

Difficulty: moderate

Exams

The final exam in this course is an open book take home exam. The exam's only question (see below) is intended to test the application of the ideas in this class in a practical setting:

If you were to redesign DNS today, how should it work? Why?

The final, due at 5pm June 9, should be about 5, but no more than 10, pages in length. The paper should be single-spaced with 1" margins and either 11 or 12pt fonts.

You are welcome to discuss the exam with other students. In fact, we encourage that. We've set up a message board for you to discuss possible answers on. While you can use any ideas presented there, all writing must be your own.