15-712 Syllabus


There are no official texts for the course. If you're not familiar with the background material, or you want to supplement the course material, you may wish to look at:

You might take a peek at the two CMU undergrad systems courses for background information on operating systems (15-410) and distributed systems (15-440).


Your final grade for the course will be based on the following weights:

The project in 15-712 is an open-ended research project, done in groups of three. The project requires a proposal, a project status report, and a final report (both written and presented).


Also available as an ical file that you can subscribe to.

Note: Class will meet on average two times per week, but we will frontload lectures a bit at the begining of the semester. This schedule is subject to change, so please hold all three days (Mon, Wed, Fri) open each week.

Date Topics Notes and Further Readings Assigned Readings
Wed 09/09 Introduction
Wisdom papers Brooks75, Hamming86, Gabriel91–Section 2.1 only
Fri 09/11 A few classics
Dennis66. Each of these papers is in the SigOps Hall of Fame. Lampson83, Saltzer84, Ritchie74
Part 1: Concurrency, Threads, and Ordering
Mon 09/14 Implementing Remote Procedure Calls
SigOps HoF paper Birrell84
Wed 09/16 Using Threads in Interactive Systems: A Case Study
Fri 09/18 Time, Clocks, and the Ordering of Events in a Distributed System
SigOps HoF paper Lamport78
Part 2: Bugs, Bugs, Bugs
Mon 09/21 Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs
SOSP'97 best paper. Bugs as Deviant Behavior (SOSP'01) Savage97
Wed 09/23 Using Model Checking to Find Serious File System Errors
OSDI'04 best paper. Towards Optimization-Safe Systems (SOSP'13 best paper) Yang04
Fri 09/25 Virtual synchrony and snapshots in distributed systems
SigOps HoF papers. Exploiting Virtual Synchrony in Distributed Systems Chandy85
Part 3: File Systems and Disks
Mon 09/28 AFS
Leases. SigOps HoF papers Howard88
Wed 09/30 The Design and Implementation of a Log-Structured File System
SigOps HoF paper. Deadline to form project groups. Rosenblum92
Fri 10/02 A Case for Redundant Arrays of Inexpensive Disks (RAID)
SigOps HoF paper. Fast'07 best paper. Guest Lecturer Garth Gibson Patterson88, Schroeder07
Mon 10/05 No class - SOSP
Wed 10/07 No class - SOSP
Part 4: Big Data Systems
Fri 10/09 MapReduce and Spark
SigOps HoF paper. NSDI'12 best paper. Dryad Dean04, Zaharia12
Mon 10/12 Naiad: A Timely Dataflow System
SOSP'13 best paper Murray13
Wed 10/14 Spanner: Google's Globally-Distributed Database
OSDI'12 best paper. BigTable (OSDI'06 best paper) Corbett12
Fri 10/16 No lecture
Course staff will be available to discuss project ideas
Mon 10/19 Dynamo: Amazon's Highly Available Key-value Store
Wed 10/21 From shared virtual memory to parameter servers (Li & Li)
SigOps HoF paper. OSDI'14 paper Li89, Li14
Fri 10/23 No class - mid-semester break
Mon 10/26 No class - PDL Retreat
Part 5: Kernels and Parallelism
Wed 10/28 Exokernel and Safe kernel extensions
SOSP'97 paper. SigOps HoF paper. Original Exokernel paper, Multikernel (SOSP'09) Kaashoek97, Necula96
Fri 10/30 The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors
SOSP'13 best paper. Project proposal due before midnight (by email to staff list). Clements15
Mon 11/02 No class
Work on project and study for midterm
Wed 11/04 Midterm Exam
Fri 11/06 Midterm Review and Project Discussions
Please come talk with staff in course room
Part 6: Transactions and Databases
Mon 11/09 On Optimistic Methods for Concurrency Control
SigOps HoF paper. Speculative Execution in a Distributed File System, Efficient Locking for Concurrent Operations on B-Trees Kung81
Wed 11/11 Concurrency Control and Recovery
Bernstein's concurrency notes - MVCC, Coordination Avoidance Franklin97
Fri 11/13 No class
Part 7: Generalized Fault Tolerance and Security
Mon 11/16 Implementing Fault-Tolerant Services Using the State Machine Approach: a Tutorial
SigOps HoF paper Schneider90
Wed 11/18 Paxos
Lamport's original Greek parable (SigOps HoF paper). Lamport's comments on original paper. Wikipedia Paxos article. Lamport01
Fri 11/20 Project meetings (all day)
Please schedule a 30 minute time slot for an Interim Project Report.
Mon 11/23 The Byzantine Generals Problem
Lamport's comments on the Byzantine Generals paper. Practical Byzantine Fault Tolerance (OSDI'99) Lamport82
Wed 11/25 No class - Thanksgiving break
Fri 11/27 No class - Thanksgiving break
Mon 11/30 Reflections on Trusting Trust, Why Cryptosystems Fail, Crisis and Aftermath
SigOps HoF paper. Write summary only for Anderson94. Thompson84, Anderson94, Spafford89
Wed 12/02 Highlights from the SOSP'15 History Day talks
SOSP'15 History Day
Fri 12/04 No class
Mon 12/07 No class
Work on project and study for midterm
Wed 12/09 Midterm 2
Fri 12/11 No class
Tue 12/15 Project Presentations
Wed 12/16 Project Presentations
Final report due before midnight tonight

Last updated: Mon Nov 23 21:19:45 -0500 2015 [validate xhtml]