CSE logo University of Washington Computer Science & Engineering
 CSE 551 - Autumn 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: Lisa Glendenning (lglenden@...)
  • Office Hours: By appointment
  • Class meetings: Mon/Wed 10:30-11:50, CSE 403
  • Recitation sections: Thursdays 4:30, CSE 203
  • 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

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

10/5: David Clark. The Design Philosophy of the DARPA Internet Protocols. SIGCOMM 88.

10/1
Project discussion and Seattle tutorial.

2 Concurrency

No class on 10/12 or 10/14; instead we'll meet 10/16

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

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

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

10/8
Individual meetings with project teams instead of section.
Problem set #1 assigned.

10/14
Project outline due at 5 p.m..

10/15
Thread programming practice.


3 Parallelism

10/19: 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/21: Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. OSDI 2004.

10/22
No section.
Problem set #1 due.

4 Transactions

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

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

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

10/29
Guest speaker at section: Steve Riley, Amazon, Cloud Computing.

Problem set #2 assigned.
5 File Systems

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

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

11/5
Design exercise #1 first draft due at noon: PCM-based storage system.

6

Consensus

No class on 11/11; instead we'll meet 11/13

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

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

11/12
Design exercise #2 first draft due at noon: High availability web service.

Design exercise #1 final draft due.

7 Virtualization

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

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

11/19
Section: Internet review (optional).

Design exercise #2 final draft due.

Problem set #3 assigned.

8 Caching and Cache Coherence

No class on 11/25

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

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

No section (Thanksgiving).

11/24
Problem set #2 due.

9 Networking

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/30: Thomas Anderson, Andy Collins, Arvind Krishnamurthy, and John Zahorjan. PCP: Efficient Endpoint Congestion Control, NSDI 2006.

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

12/3
Guest speaker at section: Steve Riley, Amazon, Protocol Insecurity.

10 Security and Wrap-up

12/7: Lampson, Computer Security in the Real World, 2001.

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

12/10
Problem set #3 due.

11 Finals Week

12/14, 8:30 am - 12:10 pm:
Final project presentations (CSE 503).



Problem Sets:


Problem Set #1

Problem Set #2

Problem Set #3


Design Exercises:


Example design exercise.

Design Exercise #1: PCM-based file system.

Design Exercise #2: High availability web service.


Project Outlines:


Examples from the previous quarter

Team Topic
Saleema, Janara, Morgan Chord
Shiri, Gilbert, Lydia Resource Discovery for Task Schedule on Mechanical Turk
Dane, Hardeep Building Trusted Software Stacks Using Trusted Platform Modules
Evan, Ben Parallel Context-Free Parsing
Daniel J., David Using a Thin Client Computer Lab as a Hadoop Cluster
Paul, Peter MapReduce in the Browser
Kevin, Sophia, Xiao Exploiting Parallelism for Object Recognition on Mobile Robots
Seong Jae, Miro ML Acceleration on GPUs
Daniel L. Approximate Nearest Neighbor on the GPU
Amit, Daniel S., Josh Distributed Queue
Emad Query Plan Optimization in SciDB: A Science-Oriented Database Management System