CSE logo University of Washington Computer Science & Engineering
 CSE 551 - Spring 2009
  551 Home   About Us    Search    Contact Info 

CSE 551: An Introduction to Computer Systems Research

  • Quals course (systems area), 5th year masters course
  • Instructor: Tom Anderson (tom@...)
  • TA: Ivan Beschastnikh (ivan@...)
  • Class meetings: Tue/Fri 1:30-2:50, EEB 42
  • Recitation sections: Thursdays 4:30-5:30, CSE 203
  • Pre-requisite: CSE 451 or equivalent
  • Credits: 4 credits (3 lecture hours plus recitation)

Course Overview:

As an experiment this year, CSE 551 will be run in a completely different fashion than in previous years: it will provide a graduate-level introduction to systems research, spanning common material now spread across 544, 551, 552, and 561. As such, it is particularly suited to those who are likely to take a single quals course in the systems area, fifth year masters students, as well as those intending to immediately jump into systems research. If successful, our intent is to introduce this as a new course in subsequent years, allowing the traditional 551 to return in the future.

Catalog Description: Advanced techniques in computer system software design, including network systems, operating systems, web servers, parallel computing, and databases. Prerequisite: CSE major and CSE 451.

Motivation: This course will provide the common intellectual foundation for systems research, suitable as a terminal course for those not interested in further study, or as a gateway course to the various specialized systems courses the department offers. The course will cover the common foundation for research in operating systems, databases, cluster and wide area distributed systems, networking, and parallel systems. These topics include:

  • Concurrency
  • Transactions and serializability
  • Virtualization/isolation
  • Network protocol design
  • Reliability out of unreliable components
  • Parallelism and cache coherence
  • System evolution
  • Workload characterization
  • Security

In addition, the course will also teach students some of the mechanics of doing systems research:

  • How to read and critique a systems research paper
  • How to set up and present a quantitative experiment

Student Deliverables:


  • Foundational readings in computer systems
  • Blog entry answering one thought question per paper
  • Oral summary of one paper in class
  • Three problem sets
  • Four design exercises
  • One student-defined team project

Readings, Blogs and Presentation: The core of the course is the reading and discussion of a set of foundational papers in computer systems. These papers cover the most important ideas in computer systems research, ones that are necessary to understand the context for any later work you might encounter. The reading is to be done before class, as we will take the papers as a starting point, not the end point of the class discussion.

For each class other than the first, we will post a small set of discussion questions, linked off the course web page, based on the reading. You are required to add a unique comment to the discussion of one of the questions before noon on the day of the class. (This is to give time for everyone to read the blog entries before class.) Note that the earlier you post, the easier it is to be unique. Please keep blog entries short: they can be anything that provides insight into the question being asked. We will automatically grant two mulligans during the quarter.

We will ask students (each student once per quarter) to kick off the class discussion by presenting a two minute synopsis of the main ideas for the paper for that class, plus the main ideas from the blog postings.

Project and Problem Sets: The course project is to be done in small teams (2-3 people), and should illustrate some interesting concurrent or distributed algorithm or system, and must include a quantitative evaluation of the work. The project can be either student defined or one defined by the instructor. Sample projects would be to implement and quantitatively evaluate Paxos (week 5), Chord (week 9), optimal congestion control (week 8), or a multithreaded, replicated web server providing both read and write operations (week 2, week 4).

There will also be three problem sets handed out during the quarter, and four extended design exercises. The problem sets and design exercises are to be done individually. The problem sets are intended to reinforce the basic material covered in the class – e.g., can you write a correct concurrent program, while the design exercises are intended to apply the ideas in the class to novel domains – e.g., one assignment will be to ask how operating system virtualization might be applied to the Internet. The design exercises will be done in two steps: an initial draft due at noon (by email) on the day of the section, followed by a revised draft due one week later (in section). This is so that student work can benefit from the discussion in section.

All assignments are due at 12:00 noon on Thursday of the week indicated, except for the final project presentations and writeup, which are due at 9AM on Monday of finals week.

Collaboration/Cheating: In our experience, students often learn more from each other than they do from the instructor. Thus, we encourage you to collaborate with your classmates, in all aspects of the course. The grading in the class is emphatically not curved; we would like nothing better than for all of you to get a 4.0.

To draw a very clear line, you may use any idea from any other person or group in the class or out, provided you clearly state what you have borrowed and from whom. If you do not provide a citation -- that is, you turn other people’s work in as your own -- that’s cheating. Anything else is fair game. Of course, we’ll be grading you on the ideas you’ve added, but you should always borrow as much as you can as a starting point – there’s no point in reinventing the wheel.

Final: This class will have no final exam.

Grading: Blogs/oral summary: 15%; Problem sets and design exercises: 50%; Project: 35%.

Syllabus and Reading List:

Week Topic Papers Assignments
1 System Design

Dennis M. Ritchie and Ken Thompson. The UNIX Timesharing System. Communications of the ACM 17(7), July 1974.

David Clark. The Design Philosophy of the DARPA Internet Protocols. SIGCOMM 88.

No assignment; project discussion and Seattle tutorial. (slides in pdf)
2 Concurrency

Butler Lampson and David Redell. Experience with Processes and Monitors in Mesa. Communications of the ACM, volume 23, issue 2, February 1980.

Pai et al., Flash: An Efficient and Portable Web Server, USENIX 1999.

Design exercise 1: Internet virtualization
3 Parallelism

Thomas Anderson, Brian Bershad, Edward Lazowska, and Henry Levy. Scheduler Activations: Effective Kernel Support for the User-Level management of Parallelism. ACM TOCS, February 1992, pp. 53-79.

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

No section; individual meetings with project teams during section time; project outline due on Wednesday; final design 1 due
4 Transactions and File Systems

(The first class will meet on Monday, April 20, 3-4:30, room TBD.)

Michael J. Franklin. Concurrency Control and Recovery.

Mendel Rosenblum and John K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Trans. on Computer Systems 10(1), February 1992, pp. 26-52.

No section (NSDI)
5 Distributed transactions and consensus
(First two papers for Tuesday.)

Paxos slides by Lorenzo Alvisi: set 1, and set 2 (Paxos slides start mid-way through the first set of slides, after the FLP overview.)

Lamport, Time, Clocks and the Ordering of Events in a Distributed System, CACM 1978.

Bernstein, Hadzilacos, and Goodman. Distributed Recovery. Chapter 7 in Concurrency Control and Recovery in Database Systems (up to 3PC).

Lamport, Paxos Made Simple, ACM SIGACT News, 2001.

Design exercise 2: PCM-based file system.
6 Virtualization

A. Bensoussan et al. The Multics virtual memory: concepts and design. Communications of the ACM, volume 15, issue 5, May 1972.

Paul Barham et al.. Xen and the Art of Virtualization SOSP 2003.

No section; individual meetings with project teams during section time; final design 2 due; project prototype due
7 Caching and Cache Coherence

(First two papers for Tuesday.)

Peter J. Denning, The Working Set Model for Program Behavior, SOSP 1967.

Breslau et al. Web Caching and Zipf-like Distributions, INFOCOM 1999.

Kai Li and Paul Hudak. Memory Coherence in Shared Virtual Memory Systems. ACM Trans. on Computer Systems 7(4), November 1989, pp. 321-359.

Design exercise 3: high availability web service
8 Networking

(First two papers for Tuesday.)

TCP/IP slides from Friday

Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM 19, 7 (July, 1976) pages 395-404.

Hari Balakrishnan. An Introduction to Wide-Area Internet Routing.

V. Jacobson. Congestion Avoidance and Control. SIGCOMM '88, pp. 314-329.

Section discussion: wireless
9 Scalability

Mockapetris and Dunlap, The Development of the Domain Name System, SIGCOMM 88.

Stoica et al., Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications, SIGCOMM 2001.

Meet with project groups to review progress.
10 Security and Wrap-up

Lampson. Hints for Computer System Design. ACM Operating Systems Review, Vol. 15, No. 5, October 1983.

Friday: Research talks by the SOSP'09 Program Committee in the Gates Commons. 8:30am - ?

Problem set #1 due June 4th at noon. Will be discussed in the section.
11 Presentations Meet in CSE303. Presentations 10AM - 12:15PM. Project presentations and writeups due Monday June 8th, at 9am.

Problem Sets:

Problem Set #1

Design Exercises:

Design exercise 1: Internet virtualization

Design exercise 2: PCM-based file system

Design Exercise #3: High availability web service.

Project Proposals:

Team Topic/Proposal
Hao Du, and David St. Hilaire Paxos Implementation and Evaluation
Joseph Devietti Deterministic Synchronization Library
Koos Kleven, and Daniel Otero Balancer of Load Across Mongrel Instances (BLAMI)
Lisa Glendenning, and Dang-Trinh Huynh-Ngoc Adapting to Node Heterogeneity in Harmony
Owen Anderson Implementation and Evaluation of a Global Memory Service
Tamara Denning Modeling a Personal Access Controller for Wireless Managed Devices with Power Constraints
Vince Zanella, Ryan McElroy, and Mark Zbikowski Paxos distributed consensus