# CSE 452: Distributed Systems

## Course Overview

Distributed systems are central to many aspects of how computers are used, from web applications to e-commerce to content distribution. This senior-level course will cover abstractions and implementation techniques for the construction of distributed systems, including client-server computing, the web, cloud computing, peer-to-peer systems, and distributed storage systems. Topics will include remote procedure call, preventing and finding errors in distributed programs, maintaining consistency of distributed state, fault tolerance, high availability, and scaling.

Alumni of this course say that it is among the most intellectually challenging courses that they have taken at UW, and among the most relevant to their future careers. We will attempt to live up to that recommendation. We believe the best way to learn the material is to implement the ideas presented in the course, and so there is a substantial programming project.

The calendar page provides a detailed topic list for the course, including readings, problem sets, and labs. In addition, we are using Gitlab, Ed, Canvas, and Gradescope for various parts of the course.

## Lecture and Sections

Lectures are MWF at 3:30 in Bagley 131. (Please double check all room assignments as they may change.) We have set up the class for Panopto lecture capture. However, we strongly encourage you to attend lecture in person, if at all possible. The material is very complex, and when you get lost (and you will - despite our best efforts) it is extremely helpful to be able to ask questions to get back on track. In fact, many students find it helpful to watch in person, and then re-watch the parts that were confusing at home. If you do watch remotely, please avoid using the speedup button - it is easy to think you understand something before you actually understand. Panopto sometimes fails for some reason or another (e.g., audio cuts out or slides don't get captured). I have a copy of last spring's lectures (recorded on my laptop) as a backup.

Sections will largely focus on the labs and (unlike many CSE classes) you will need to attend to be able to complete the assignments. Sections are not Panopto captured - you must attend live.

## Course Staff

• Tom Anderson, instructor tom@cs.washington.edu
• Ani Canumalla, TA anirudhc@cs.washington.edu
• Xun Cao, TA, whdecx@cs.washington.edu
• Logan Gnanapragasam, TA gnanabit@cs.washington.edu
• Theo Gregersen, TA theoag@cs.washington.edu
• Nachiket Karmarkar, TA nkarm@cs.washington.edu
• Bryan Lim, TA bryanlim@cs.washington.edu
• Aman Mohammed, TA amanm4@cs.washington.edu
• Guramrit Singh, TA gsingh98@cs.washington.edu
• Samuel Vanderlinda, TA samvande@cs.washington.edu
• Eddy Zhou, TA zty0911@cs.washington.edu

You can email the entire staff (including Tom, despite the fact that the email address says "TAs") at cse452-tas@cs.washington.edu, but we prefer you make a private post on Ed if possible.

## Staff Contact

The best way to contact the staff is to make a post on Ed. If your question is likely to be useful to other students, please consider making it public. (You can make the post "anonymous" to hide your identity from your classmates, but note that course staff can still see your identity on anonymous posts. See anonymous feedback at the very bottom of this page for submitting feedback without revealing your identity to course staff.) If your message is not relevant to other students, make it private. We prefer you send messages via Ed if at all possible, because it allows any staff member to assist you. If you need to contact an individual staff member directly, you can also use email.

## Assignments

There are three kinds of assignments in this class.

• Labs. Four total. The first lab is done individually; the remainder are done in teams of two. The last lab has three separately graded parts. Typically due on Friday night.
• Problem sets. Most lecture topics (which might spread across a few lectures) have a problem set associated with them. Some of these are due before lecture (formative); others will be due a week after the last lecture for a topic (evaluative). Formative assignments can be done in groups of up to three; evaluative are to be done individually.
• Blog posts. During the last three weeks of the quarter, we will assign and discuss six research papers. Prior to class you will write a post on the discussion board about some aspect of the paper. Due before the lecture in which the paper is discussed.

See the sections below for more information on each kind of assignment, as well as the sections on grading, the late policy, and academic honesty.

### Labs

The core of the course is to build a highly available, scalable, fault tolerant, and transactional key-value store. Key-value stores are widely used in cloud computing. The project is written in Java, derived from a similar one designed for the MIT graduate distributed systems course. A hallmark of our project infrastructure is extensive support for thorough testing and debugging. Each lab has a model-checking-based test suite that you can use to validate your implementation.

Lab 0 and Lab 1 of the project are to be done individually. (Note that Lab 0 does not have a turnin.) The other labs (2-4) are to be done with a partner. After the introductory labs (lab 0 and lab 1), each of the other labs is due every two or three weeks.

The labs are autograded by a model checker, and that means you will need to come up with solutions that work in all cases. Except for the writeup, the labs are (for the most part) self-grading - we give you all of the test cases we run.

The best way to write code that works in all cases do this is to carefully think your design before writing any code. Design before code is especially important for distributed systems where the number of possible code paths is exponential in the number of messages, the cost of uncaught errors in production code is enormous, and it is often infeasible to catch every possible error through testing.

This is very different from other CSE classes you may have taken. If you think we are just saying that and we don't really mean it, please understand that it may take you as much as ten times as long to complete the assignments if you start writing code before you carefully think through the design with your partner. Debugging typos can be laborious but is a reality we all face. Debugging distributed system design errors by testing is extremely time consuming.

To encourage you to design then code, we ask for a short design document for each lab, worth a small portion of the total value of the lab, due when you turn in the lab. You and your partner should agree on the design document before writing any code. Of course, you may find from time to time that you need to update the design, but you want to try to minimize that. As part of that document, we also ask you to provide a post-mortem: what worked for you, and what didn't, in completing the lab.

We strongly recommend you get an early start on the labs. Many students underestimate the difficulty of the assignments, and leave themselves too little time to finish in time. The most common comment about the labs is that students wished they had gotten an earlier start. See below for the late policy.

### Problem Sets

For most lecture topics (which may span one or more class meetings), we will assign a small short problem set specific to that topic. These assignments will appear in Gradescope. Problem sets come in one of two types: formative (group) and evaluative (individual). The formative assignments are intended to give you a deeper understanding of the solutions presented in lecture. These are generally due before lecture, and are lightly graded. Often there is no single right answer. These can be done in groups of up to three (these groups often will be, but do not need to be, the same as your project groups).

Evaluative problem sets test the understanding of the material presented in lecture. These are to be completed individually, typically due one week after the last class that covers that topic. However, we encourage you to work on them as soon as possible after the corresponding class, so you have time to ask questions if anything is confusing. See below for the late policy.

### Readings and Blogs

There is no textbook for this course. Instead, we will assign various tutorial and research papers. Although we do not have assignments directly relating to the tutorials, they are important for understanding the material in the lectures, labs, and problem sets.

In the final three weeks of the class, we will shift gears and read and discuss six papers describing various practical distributed systems. For these papers, we ask students to submit a blog post on each paper due prior to the class where the topic is discussed. The blog discussions are submitted on canvas, and the discussion prompt will include suggestions as to possible topics to address. Your blog post may also extend a discussion, or answer a question, posed by someone else.

See below for the late policy.

The class will be graded on an additive points system.

• Lab 1: 160 points (note the lab 1 tests sum to 320, so for this lab points are divided by 2) + 10 design document
• Lab 2: 325 points + 40 design document
• Lab 3: 365 points + 50 design document
• Lab 4: 495 points + 50 design document
• Evaluative problem sets: 275 total points
• Formative problem sets: 80 total points
• Blog posts: 150 total points, 25 for each of 6 papers
• Total points possible: 2000
There is no midterm or final exam.

The course is not curved. Your grade on a 4.0 scale is computed by the following formula. $\min\left( \left.\left\lfloor\frac{\mathrm{points}}{40}\right\rfloor \middle/ 10 - 0.6 \right.,\ 4.0 \right)$ In other words, your grade will be computed by the following table:

Points Grade on 4.0 scale
≥1840 4.0
≥1800 3.9
≥1760 3.8
≥1720 3.7
≥1680 3.6
≥1640 3.5
≥1600 3.4
≥1560 3.3
...
≥1440 3.0
...
≥1320 2.7 (grad sat)
...
≥1040 2.0 (undergrad sat)
...

This grading scheme may be somewhat unfamiliar to you. We will discuss it on the first day of lecture. Be sure you understand it, and feel free to ask any questions about it.

An important consequence the additive points-based grading scheme is that there is a sense in which every assignment is optional. If you are unable to complete some assignment, simply make sure to complete the remaining ones - we give you room to miss points and still get a good grade. For example, if you miss 15% of the available points, that is still some form of an A grade.

Since you will receive the same number of points as your partner for your combined work on labs 2-4, it is essential during partner-matching that you communicate expectations about your grade target. If you find yourself stuck in a situation where your partner wants to do significantly more or less work than you do, please contact the staff.

Most students find that they are able to complete all of the assignments to a high degree of quality, but that the assignments require a decent amount of effort. Students find the class time-consuming but rewarding, and so grades in this class are generally high.

If you are taking the class S/NS, note that per university policy, undergraduates receive S credit for any grade 2.0 or higher, while graduate students (including BS/MS students) receive S credit for any grade 2.7 or higher. Thus, an undergraduate would need to earn at least 1040 points to receive S credit, while a graduate student would need to earn at least 1320 points to receive S credit.

## Late Policy

Our late policy is designed to give students maximal flexibility without having to ask us for permission in most cases, while still allowing us to grade assignments and get them back to students in a timely fashion. If you have an extenuating circumstance that causes you not to be able to complete the work on time, especially if due to something outside of your control (such as your lab partner has an illness or drops the class), please contact the staff or email the instructor. Often, we are able to work something out that is agreeable to everyone involved.

Each kind of assignment has a separate late policy. Be sure you understand the differences. Contact course staff if you have any questions.

• All assignments, regardless of late policy or extensions, must be turned in by the end of the day Thursday June 9, unless the instructor has given specific permission (generally only available in the case of illness or if the final grade would be below a 2.0).
• Each lab (except the last one obviously!) comes with a 72 hour grace period, during which work is accepted without penalty. We then deduct 1% off your score, just for that assignment, for each additional day that it is late. In other words, if you are making progress, even slowly, you should keep working on the lab, but if you are stuck you should go ahead and turn it in. Since turning assignments in late cuts into the available time you have for the next lab, only use this flexibility if necessary.
• If you turn in a lab and later on discover that you have a solution that would receive a higher grade from the automated grader, you may resubmit it for a regrade for up to 50% of the missing points. (You need to let us know you plan to do this.) Note that we will not regrade the design document. This case is somewhat common for students who miss points on lab 3, since lab 4 builds on lab 3.
• Problem sets have a 24-hour grace period, during which work is accepted without penalty. No credit is granted after the grace period expires.
• Blog posts are due before the beginning of the lecture in which the paper is discussed. You may turn in a blog post within 24 hours after the original deadline for half credit. After 24 hours, no credit will be given.

Note that, unlike some other course policies you might be familiar with, in this class there is no cap on how much total grace time you can use over the quarter. You can use the grace period on every single problem set and lab (except the last one) and still get full credit. Note that blog posts are different, since the 24 hour grace period on a blog post is for half credit.