15-712 Syllabus

• 15-712 Home
• Syllabus
• Exams
• Announcements
• Summaries
• Project

Textbooks

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

• Operating Systems Concepts, by Silberschatz, Galvin, and Gagne. This and the below text cover mostly background material that we assume students will be generally familiar with (both of these texts go beyond what we'll expect).
• Modern Operating Systems, 2nd edition, by Andrew S. Tanenbaum.
• Computer Networks: A Systems Approach, third edition, by Larry Peterson and Bruce Davie. It is available in the CMU Bookstore. Covers background networking material that we assume students will be generally familiar with.
• Advanced Programming in the Unix Environment by W. Richard Stevens, Addison-Wesley, 1993.
• Unix Network Programming: Networking APIs: Sockets and XTI (Volume 1) by W. Richard Stevens.
• The Art of Computer Systems Performance Analysis, by Raj Jain.
• Distributed Algorithms, by Nancy Lynch
• Remzi Arpaci-Dusseau's OS lecture notes are a great, free, online resource for background ugrad OS concepts.

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

Suggested Readings

You may also find the following readings useful:

• The Mythical Man-Month: Essays on Software Engineering, by Fred Brooks
• Scale and performance in a distributed file system, Howard, Kazar, Menees, Nichols, Satyanarayanan, Sidebotham, and West. ACM Transactions on Computer Systems (Feb 1988). This paper describes AFS, and is cited by most papers that evaluate filesystem performance. Many people simply know this paper as Howard88. You may find this interesting because you use AFS, and you may need to cite this if you build a storage system.
• End-to-end arguments in system design, Saltzer, Reed, and Clark. ACM Transactions on Computer Systems (Nov 1984). This paper presents the design principle that functionality should be end-to-end. For example, data should be verified or encrypted at the source and destination rather than along the way. Mechanisms in the middle tend to be redundant.

Grading

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

• 40% Project
• 20% Midterm exam
• 20% Final exam
• 20% Paper Summaries, homeworks, and participation

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).

Schedule

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

Date	Topics	Notes	Readings
Wed 09/06	Introduction [pdf]	Wisdom papers	Brooks75, Hamming86, Gabriel91–Section 2.1 only, Lampson83, Saltzer84, Ritchie74
Part 1: Concurrency, Threads, and Ordering
Fri 09/08	Implementing Remote Procedure Calls [pdf]	SigOps HoF paper	Birrell84
Mon 09/11	Using Threads in Interactive Systems: A Case Study [pdf]		Hauser93
Wed 09/13	Time, Clocks, and the Ordering of Events in a Distributed System [pdf]	SigOps HoF paper	Lamport78
Part 2: Bugs, Bugs, Bugs
Fri 09/15	Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs [pdf]	SOSP'97 best paper. Bugs as Deviant Behavior (SOSP'01)	Savage97
Mon 09/18	Using Model Checking to Find Serious File System Errors [pdf]	OSDI'04 best paper. Towards Optimization-Safe Systems (SOSP'13 best paper)	Yang04
Part 3: File Systems and Disks
Wed 09/20	AFS [pdf]	Leases. SigOps HoF papers	Howard88
Fri 09/22	No Class
Mon 09/25	The Design and Implementation of a Log-Structured File System [pdf]	SigOps HoF paper. Deadline to form project groups.	Rosenblum92
Wed 09/27	A Case for Redundant Arrays of Inexpensive Disks (RAID) [pdf]	SigOps HoF paper. Fast'07 best paper.	Patterson88, Schroeder07
Part 4: Big Data Systems
Fri 09/29	MapReduce and Spark [pdf]	SigOps HoF paper. NSDI'12 best paper. Dryad	Dean04, Zaharia12
Mon 10/02	No lecture	Course staff will be available to discuss project ideas
Wed 10/04	Naiad: A Timely Dataflow System [pdf]	SOSP'13 best paper	Murray13
Fri 10/06	Dynamo: Amazon's Highly Available Key-value Store [pdf]		DeCandia07
Mon 10/09	No Class
Wed 10/11	Paxos [pdf]	Lamport's original Greek parable (SigOps HoF paper). Lamport's comments on original paper. Wikipedia Paxos article.	Lamport01
Part 5: Kernels and Parallelism
Fri 10/13	From shared virtual memory to parameter servers (Li & Li)	SigOps HoF paper. OSDI'14 paper	Li89, Li14
Mon 10/16	No Class
Wed 10/18	Review
Fri 10/20	Mid-Semester Break
Mon 10/23	Exokernel and Safe kernel extensions	SOSP'97 paper. SigOps HoF paper. Original Exokernel paper, Multikernel (SOSP'09)	Kaashoek97, Necula96
Wed 10/25	No class, please review papers
Fri 10/27	Midterm Exam
Mon 10/30	The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors	SOSP13 best paper.	Clements15
Wed 11/01	No class
Fri 11/03	No class
Part 6: Transactions and Databases
Mon 11/06	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/08	Project Discussions With Staff
Fri 11/10	No class
Mon 11/13	Concurrency Control and Recovery	Bernstein's concurrency notes - MVCC, Coordination Avoidance	Franklin97
Part 7: Generalized Fault Tolerance and Security
Wed 11/15	No class OR 3 groups of project meetings
Fri 11/17	Project Meetings (all day)	Please schedule a 30 minute time slot for an Interim Project Report.
Mon 11/20	The Byzantine Generals Problem	Lamport's comments on the Byzantine Generals paper. Practical Byzantine Fault Tolerance (OSDI'99)	Lamport82
Wed 11/22	No Class, Gobble Gobble
Fri 11/24	No Class, Gobble Gobble
Mon 11/27	Reflections on Trusting Trust, Why Cryptosystems Fail, Crisis and Aftermath	SigOps HoF paper. Write summary only for Anderson94.	Thompson84, Anderson94, Spafford89
Wed 11/29	No class
Fri 12/01	No class
Mon 12/04	Highlights from the SOSP'15 History Day talks	SOSP'15 History Day. Guest lecture.
Wed 12/06	Midterm 2
Fri 12/08	No class. We grade, you project.
Tue 12/12	Project Presentations (tentative date)
Wed 12/13	Project Presentations	Final report due before midnight tonight