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% Quiz 1
• 20% Quiz 2
• 20% Paper Summaries, homeworks, and participation

The quizzes will be in-class, one near midterm and one near the end of the semester.

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.

Note: Class will meet on average twice per week, but there will be a few weeks where we only meet once and a few where we meet thrice. Most weeks are Monday-Wednesday, but please consult the schedule!

Date	Topics	Notes	Readings
Mon 01/11	Introduction [pdf] [key]		Lampson84, Gabriel91–Section 2.1 only, Hamming
Part 1: Concurrency, Threads, Parallelism, Ordering, and Races
Wed 01/13	Implementing remote procedure calls [pdf] [key]		Birrell84
Fri 01/15	TA-led undergrad OS and networking review [pdf] [key]	Attendance optional. outline
Mon 01/18	MLK Day - No Class
Wed 01/20	Using threads in interactive systems: A case study [pdf] [key]		Hauser93
Fri 01/22	Time, Clocks, and the Ordering of Events in a Distributed System [pdf] [key]		Lamport78
Mon 01/25	Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs [pdf] [key]	Mentioned in class: Bugs as Deviant Behavior.	Savage97
Part 2: Storage and Remote DMA
Wed 01/27	A Case for Redundant Arrays of Inexpensive Disks (RAID) [pdf] [key]	Therac-25, NY Times article	Patterson88, Schroeder07
Fri 01/29	AFS	Leases paper	Howard88
Mon 02/01	Separating data and control transfer in distributed operating systems, The Direct Access File System	no DeBergalis required. NFS over RDMA paper mentioned in class.	Thekkath94, DeBergalis03
Wed 02/03	The Design and Implementation of a Log-Structured File System [pdf] [key]		Rosenblum92
Fri 02/05	Cluster-based storage: NASD and the Google File System	Project groups and initial ideas due	Gibson98, Ghemawat03
Mon 02/08	No Lecture -- meetings with course staff to discuss project proposal
Fri 02/12	MapReduce and Dryad	Project proposal due (in class)	Dean04, Dryad
Mon 02/15	OS Architecture and Extensibility: SPIN and the Exokernel [pdf] [ppt] [key]		Bershad95, Kaashoek97
Wed 02/17	Kernels and Parallelism		Multikernel
Fri 02/19	No class
Part 3: Transactions and Databases
Mon 02/22	On Optimistic Methods for Concurrency Control [pdf] [key]	For further reading, see Spectulative Execution in a Distributed File System	Kung81
Wed 02/24	No class
Mon 03/01	Efficient Locking for Concurrent Operations on B-Trees [pdf] [key]	See also Chord-Sigcomm2001 if you'd like more details.	Lehman81
Wed 03/03	1st midterm
Fri 03/05	No class - Mid-semester break	Why does mid-semester break co-occur with spring break?
Mon 03/08	No class - spring break
Wed 03/10	No class - spring break
Fri 03/12	No class - spring break
Mon 03/15	Post Midterm Review
Wed 03/17	Project meetings (all day)	Please schedule a 30 minute time slot
Fri 03/19	No class (possibly more project meetings)
Mon 03/22	Principles of Transaction-Oriented Database Recovery [pdf] [key]	Bernstein's concurrency notes - MVCC, Why snapshot isolation is useful, short paper about an anomaly in snapshot isolation, mentioning history.	Franklin97
Wed 03/24	BigTable		Chang06
Fri 03/26	No Class
Part 4: Generalized Fault Tolerance
Mon 03/29	Dynamo		Vogels07
Wed 03/31	Paxos [pdf] [key]	Wikipedia Paxos article. Lamport's original Greek parable.	Lamport01
Fri 04/02	No class
Mon 04/05	The Byzantine General's Problem, Practical Byzantine Fault Tolerance [pdf] [ppt]	Lamport's comments on the Byzantine Generals paper (see also here).	Castro99, Lamport82
Part 5: Security
Wed 04/07	Reflections on Trusting Trust, Why Cryptosystems Fail, Crisis and Aftermath [pdf] [key]		Thompson84, Anderson94, Spafford89
Fri 04/09	No class
Mon 04/12	The protection of information in computer systems [pdf] [key]	For additional info, see The Flask Security Architecture paper that describes the underpinnings of SELinux and the Flume paper from SOSP 2007 on DIFC.	Saltzer75
Wed 04/14	No class
Fri 04/16	No class
Mon 04/19	A Logic of Authentication [pdf] [key]	See also Dos and Don'ts of Client Authentication on the Web.	Burrows90
Wed 04/21	No class
Fri 04/23	Midterm 2 - TAKE HOME - will be released by Friday, no class
Mon 04/26	SecVisor		SecVisor
Wed 05/05	Project Presentations, 1:00 - 3:00, room 9115-GHC
Thu 05/06	Project Presentations, 1:00 - 3:30, room 8102-GHC
Fri 05/07	Final report due