CSE 552: Parallel and Distributed Systems, Spring 2019

Overview

This course will focus on correctness. Distributed systems are particularly difficult to make correct. Concurrent updates to distributed state introduce subtle race conditions. Component failures are inevitable, and "distributed" means the system is expected to proceed despite them. What invariants and progress conditions ensure that systems operate correctly despite concurrency and failures?

This iteration of the class will NOT cover parallel computing.

Further, we'll assume basic knowledge of distributed-systems topics, including: remote procedure calls (RPC), two-phase commit, distributed time, serializability, and MapReduce. This can be obtained by taking CSE 550 before CSE 552 (which is the normal order). A motivated student will be able to pick up these topics on their own. See the background section below for more information. Students having taken an undergraduate distributed-systems class will find about 25% of the material will overlap; in particular, it's permitted to take both CSE 452 and CSE 552.

Research Project: A major part of the course will be an independent research project on a topic of your choosing related to distributed systems, with team members of your choosing. A strict requirement is that every project must have a quantitative result — in other words, purely paper designs are not sufficient.

Course Reading and Discussion: Another major part of the course will be a group discussion of various assigned papers both before and during class. The goal will be to develop your ability to uncover the broader implications of research papers. Most systems research starts with this process: what can one conclude from a research result, beyond what's written by the authors?

Mailing List

Course Reading and Discussion

For each class except the first, we'll have a forum thread that any student may post to and read. Each student must, before class begins, post a paragraph that makes an interesting point about one of that class's papers.

The class discussion will be divided into two parts. First, we'll discuss the plain content of the paper: What did the authors think the paper was about? Second, we'll examine the subtext and context of each paper: What do we (the lecturers and the students) think is really interesting about the paper? For instance, what limits and opportunities does the paper miss?

For the first part of the discussion, we'll lecture on mechanical elements of the papers that are hard to discuss without prepared slides. We'll then kick off an interactive discussion. The class-participation portion of your grade will depend on the extent to which you participate meaningfully in each such discussion.

Prior to each class, we'll post a short list of questions to get the discussion started, but we'll also cover topics from the forum thread and topics that arise naturally from the class discussion.

At the end of each class, we'll spend 5–10 minutes preparing you to read the papers for the next class. We'll provide background material that provides context for them, and we may suggest questions to think about while reading them.

Discussion Board

https://canvas.uw.edu/courses/1272963

• Course discussion. This is a great place for you to post questions about papers, problem sets, or research projects; to look for a project partner; or anything else class-related.

• Paper discussions. For each class except the first, we'll have a forum thread that any student may post to and read. Each student must, before class begins, post a paragraph that makes an interesting point about one of the papers assigned for that class.

  Your posts will be graded using the following simple 2-bit scale. If you don't post before the class, you get a 0. If you post something, but if there are significant problems with what you've posted, e.g., we're not convinced you read and thought about the paper, you get a 1. If you post something interesting and thoughtful, you get a 2; we expect most of your posts to get this grade. Once in a while, if you post something that is surprisingly insightful or otherwise exceptional, you'll earn a 3; these grades will be rare.

Background

• Implementing Remote Procedure Calls
• Introduction to Distributed Systems Design
• Time, Clocks, and the Ordering of Events in a Distributed System (up to, but not including, the section on physical clocks)
• Concurrency Control and Recovery in Database Systems (only Chapter 7, Distributed Recovery, and only up to, but not including, three phase commit)
• MapReduce: Simplified Data Processing on Large Clusters
• Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency

Schedule of Non-Class Events

Class Paper Schedule

Here's the schedule of papers to be discussed during class. For each class, there's one primary paper you must read before class, and one or more optional papers we encourage you to also read before class. Your post to the forum thread before class can be on either the primary paper or an optional paper.

Research Project and Presentation

We've provided a few suggestions for project ideas. But you're welcome (indeed, encouraged!) to devise your own project ideas not on that list.

The project will be due in five steps:

• Initial one page project proposal, due April 12 at 5pm
• Three-page outline, including a complete introduction, due May 3 at 5pm
• Five-page version, including a complete discussion of related work, due May 24 at 5pm
• Final research project paper, due Tuesday, June 11 at 5pm
• Final research project presentation, with each project group given a 30-minute time block on June 12

Everybody registered for the course should already have had an instructional UNIX account created for them by the department support staff, and have been notified of it. Using this account, you can remotely log into (via ssh) the attu.cs.washington.edu compute cluster. You can find more information about instructional resources here.

If the compute cluster doesn't meet your needs, you may want to consider one of the following experimental platforms, which we can help you get access to:

• Microsoft Azure and Amazon Web Services: Azure and AWS allow anyone to rent a set of virtual machines, and one use is to run experiments. For this route, you need to pay for any computation/bandwidth charges yourself, or apply for free Azure credits at this link.
• CloudLab: CloudLab is a testbed for experimenting with cloud-scale distributed systems. It provides bare-metal access to machines, which provides flexibility in experimental setup and isolation between multiple experimenters. Its machines are distributed across three sites: Utah, Washington, and South Carolina.
• Emulab: Emulab is a collection of experimental machines in single machine room, which can be configured to run experiments on an emulated network configuration. For example, nodes can be set up to emulate clients and servers communicating with typical latencies and bandwidths of a wide area network. Node resources are dedicated, and so results are more repeatable than in PlanetLab — this can be both a good thing (when testing), and a bad thing (when validating robustness).
• iPlane: iPlane is a continuous trace of the current public Internet topology, using a set of tools developed at UW. If you need to evaluate a wide area distributed systems against typical topologies, iPlane is a good fit. There are also traces of the distribution of access link bandwidths for client machines, as well as the distribution of failure probabilities for client and server machines.
• Measurement Lab: Measurement Lab is a platform for measuring Internet properties. Its extensibility makes it a useful alternative to iPlane if iPlane lacks the measurements you need.

Problem Sets

• Problem Set 1
  out: April 1
  due: April 19 at 5pm
  
• Problem Set 2
  out: April 19
  due: May 10 at 5pm
  
• Problem Set 3
  out: May 6
  due: May 31 at 5pm
  

Final

The final will constitute 20% of your grade. Its questions will be drawn from the required portions of the reading list.

Grading

• Participation in online forum and class discussions: 15%
• Problem sets: 15%
• Research project: 50%
• Final exam: 20%