CSE logo University of Washington Computer Science & Engineering
 CSE 550 - Autumn 2010
  550 Home   About Us    Search    Contact Info 

CSE 550: An Introduction to Computer Systems Research

  • Quals course (systems area), 5th year masters course
  • Instructor: Tom Anderson (tom@cs...)
  • TA: Dane Brandon (dbrandon@cs...)
  • Office Hours: By appointment
  • Class meetings: Mon/Wed 10:30-11:50, EEB 031
  • Recitation sections: Thursdays 4:30, CSE 403
  • Pre-requisite: CSE 451 or equivalent
  • Credits: 4 credits (3 lecture hours plus recitation)

Schedule and Reading List:

  Week   Topic Papers Assignments
1 System Design/Concurrency

No class on 10/4; instead we'll meet 10/1 in CSE 203

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

Background reading (optional): Andrew Birrell, An Introduction to Programming with Threads, DEC SRC Research Report 35, January 1989.

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

Section 9/30: Projects, measurements, QA
Problem Set #1 out.
2 Concurrency

No class on 10/4

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

Section 10/7: Thread programming practice.
3 Parallelism

10/11: 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.

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

Project outline due at noon Wednesday Oct 13th
DE#1 out. Rough draft due at noon Thursday Oct 21st
Final draft due at 4:30pm Thursday Oct 28th
Section 10/14: More threading practice.
4 Transactions

Background reading: Michael J. Franklin. Concurrency Control and Recovery.

10/18: Gray et al. The Recovery Manager of the System R Database Manager. ACM Computing Surveys, 1981.

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


Problem set #1 due 4:30pm.
DE#1 rough draft due at noon.
5 File Systems

10/25: 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.

10/27: Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File System. SOSP 2003.

10/27: Proj. progress report due at noon.

10/28: DE#1 final draft due at 4:30pm.

Problem Set #2 out

Section 10/28
Individual team meetings.



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

11/3: Lamport, Paxos Made Simple, ACM SIGACT News, 2001.

Section 11/4
DE#2: High availability web service.
Rough draft due at noon.

7 Virtualization

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

11/10: Paul Barham et al. Xen and the Art of Virtualization SOSP 2003.

(No section on 11/11; instead it will meet 11/12 at 10:30) Section 11/12: Internet basics (TCP/IP).
8 Caching and Cache Coherence

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

11/17: James J. Kistler and M. Satyanarayanan. Disconnected Operation in the Coda File System

(No section on 11/18; instead it will meet 11/19 at 10:30) Section 11/19: Internet basics (TCP/IP).
9 Networking

No class 11/24. Happy Thanksgiving.

Background reading: Salzer and Kaashoek. The Network as a System. Chapter 7 in Principles of Computer System Design. MIT OpenCourseWare, 2009.

Should read: Hari Balakrishnan. An Introduction to Wide-Area Internet Routing. Unpublished.

11/22: David Clark. The Design Philosophy of the DARPA Internet Protocols. SIGCOMM 88.

No Section. Gobble gobble!

10 Networking

11/29: Thomas Anderson, Andy Collins, Arvind Krishnamurthy, and John Zahorjan. PCP: Efficient Endpoint Congestion Control, NSDI 2006.

12/1: John John, Ethan Katz-Bassett, Arvind Krishnamurthy, Thomas Anderson and Arun Venkataramani. Consensus Routing: The Internet as a Distributed System. NSDI 2008.

Team project meetings. Progress reports due noon Wed.
11 Security and Wrap-up

Optional reading: Lampson, Computer Security in the Real World, 2001.

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

Problem set #3 due. No section.

12 Finals Week

12/13, 9am Room 203
Final project presentations.

Project Outlines:

Project outline due at noon Wednesday Oct 13th

Examples from the previous quarter

Example final project and presentation Dane's final paper Dane's final presentation

Problem Sets:


Problem Set #1 Due 10/21 4:30pm

Problem Set #2 Due 11/19 10:30am

Problem Set #3 Due 12/9 4:30pm

Faloutsos paper for PS#3

Design Exercises:


Example design exercise.

DE#1 rough draft due at noon Thursday Oct 21st
DE#1 final draft due at 4:30pm Thursday Oct 28th

Design Exercise #1: PCM-based file system.

DE#2 rough draft due at noon Thursday Nov 4th
DE#2 final draft due at 4:30pm Tuesday Nov 16th

Design Exercise #2: High availability web service.

Misc. Stuff

Design Pattern for Concurrent Programming