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

CSE 490H: Distributed Systems


  • Undergraduate course, 5th year masters course (552)
  • Instructor: Tom Anderson (tom@cs...)
  • Grad TA: Vincent Liu (vincent@cs...)
  • Ugrad TA: Allison Obourn (aeobourn@cs...)
  • Office Hours: Mondays, 2:30 - 3:30
  • Class meetings: Mon/Wed/Fri 9:30-10:30, EEB 003
  • Quiz sections: Thursdays 8:30 and 9:30, MOR 225
  • Pre-requisite: (CSE 351 OR CSE 378) and (CSE 326 OR CSE 332) Recommended: CSE 451
  • Credits: 4 credits (3 lecture hours plus section)

Schedule and Reading List:


  Week   Topic Papers Notes Assignments
1 Introduction and Client/Server

1/3: Google. Introduction to Distributed System Design.

1/5: Remote procedure call
Andrew Birrell and Bruce Nelson. Implementing Remote Procedure Calls. ACM TOCS 1984.
Google, Protocol Buffers Developer Guide.

1/7: Remote method invocation
Wollrath, Riggs and Waldo. A Distributed Object Model for the Java System. USENIX Computing Systems, 1996.

   
2 Client/Server and Memory Consistency and Cache Coherence

1/10: Distributed Debugging
Lamport, Time, Clocks and the Ordering of Events in a Distributed System, CACM 1978.(up to, not including, the section on physical clocks)

1/12: Cache Coherence, part 1
Kai Li and Paul Hudak. Memory Coherence in Shared Virtual Memory Systems. ACM TOCS 1989.

1/14: Cache Coherence, part 2

1/12
Cache Coherence 1

1/14
Cache Coherence 2

1/14: Project part 1 due: client-server
3 Memory Consistency and Cache Coherence and Failure Recovery and Fault Tolerance

1/17: Martin Luther King Day, no class

1/19: Eventual consistency
Jay Kistler and M. Satyaranayaman. Disconnected Operation in the Coda File System. ACM TOCS1992.

1/21: Transactions
Robert Hagmann. Reimplementing the Cedar File System Using Logging and Group Commit. SOSP 1987.

1/19
Ivy/AFS/coda/bayou

 
4 Failure Recovery and Fault Tolerance and

1/24: Distributed Transactions, part 1
Bernstein, Hadzilacos, and Goodman. Distributed Recovery. Chapter 7 in Concurrency Control and Recovery in Database Systems.(up to, and not including, three phase commit)

1/26: Distributed Transactions, part 2

1/28: State Machine Replication
Bernstein and Newcomer. Replication. Chapter 9 in Principles of Transaction Processing.

1/24
Transactions 1

1/26
Transactions 2

1/28
Two phase commit

1/28: Project part 2 due: cache coherence
5 Paxos and GFS

1/31: Paxos, part 1
Lamport, Paxos Made Simple, ACM SIGACT News, 2001.

2/2: Paxos, part 2

1/31 & 2/2
Paxos slides

2/4
Replication

 
6

Cloud Programming

2/7: GFS
Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File System. SOSP 2003.

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

2/11: Dryad
Yu et al. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. OSDI 2008.

2/7
GFS

2/9
MapReduce
MapReduce Design Patterns

2/11
Dryad
DryadLINQ

2/11: Project part 3 due: distributed transactions
7 Cloud Programming and Beyond

2/14: BigTable
Chang et al. BigTable: Distributed Storage System for Structured Data. OSDI 2006.

2/16: BitTorrent
Piatek et al. Do Incentives Build Robustness in BitTorrent? NSDI 2007.

2/18: MegaStore
Baker et al. Megastore: Providing Scalable, Highly Available Storage for Interactive Services. CIDR 2011.

2/14
BigTable

2/18
MegaStore slides

2/18
MegaStore notes

 
8 Presidents Day/Hack Week

2/21 - 2/25: Hack Week

  2/25: Project part 4 due: paxos
9 Beyond the Cloud

2/28: Dynamo
DeCandia et al. Dynamo: Amazon?s Highly Available Key-Value Store. SOSP 2007.

3/2: PNUTS
Cooper et al. PNUTS: Yahoo?s Hosted Data Serving Platform, VLDB 2008

3/4: Hints and wrapup
Lampson. Hints for Computer System Design. ACM SIGOPS OSR 1983.

2/28
Dynamo slides
Dynamo notes

3/2
PNUTS

 
10 Hack Week

3/7 - 3/11: Hack Week

   
 
11 Finals Week

3/15: Project demonstrations

3/16: Final Exam, 8:30am - 10:20

 

3/14: Project part 5 due: peer to peer Facebook

3/14: M552 project add-on due



Project:


DropBox

Assignment 1

Introduction      Specification      Framework

Assignment 2

Specification      Introduction to Synoptic      Framework Version 2

Assignment 3

Specification      Framework With extra byte I/O streams

Assignment 4

Specification

Assignment 5

Specification

Assignment 6

Specification

Problem Sets:


Problem Set #1 Due: 8:30am, Thursday, March 10, 2011



Misc. Stuff


Paxos

2PC