15-440: Distributed Systems Syllabus

Textbook

Distributed Systems
Maarten Van Steen & Andrew S. Tanenbaum
Published by CreateSpace Independent Publishing Platform, ISBN 978-1543057386, 3rd edition.

The lecture notes will be available after each lecture to assist with studying -- please read them as they often contain material that goes beyond just what we covered in lecture! For supplemental reading in particular areas, you may find one of the following texts, available from the library, helpful:

Computer Networks: A Systems Approach, fourth edition, by Larry Peterson and Bruce Davie.
Operating Systems Concepts seventh edition, by Silberschatz, Galvin and Gagne
For the projects, please see Dave's Notes on Software Engineering for Systems Hackers.
For programming, see Unix Network Programming: Networking APIs: Sockets and XTI (Volume 1) by W. Richard Stevens.
Advanced Programming in the Unix Environment by W. Richard Stevens, Addison-Wesley, 1993.

Grading

Your final grade for the course will be based on the following weights for the components of the course. The weights of the individual projects will vary slightly by the difficulty of the project:

45% Projects
15% Homework
20% Midterm 1
20% Midterm 2

The midterms will be in-class, closed-book exams. While they may cover all material to that point in the class, their content will emphasize the material covered since the previous exam. The final exam will be a closed-book exam, covering material from the whole semester, with slight emphasis on material covered since the last midterm.

For more information about the project component, see the assignments page.

The homework will combine both textbook-like questions as well as hands-on experimental exercises. There will be three homework assignments.

Because of the importance of understanding both the theoretical and hands-on elements of systems, students must pass all three components of the course (homeworks, exams, and the projects) in order to receive a passing grade for the course. This does not affect the actual letter grade assignment unless one of the components is not completed to a passing standard.

Schedule

Date	Instructor	Topics	Notes	Readings
Tue 08/28	yuvraj	Introduction [pdf] [ppt]		Tanenbaum 1.1, 1.2
Thu 08/30	daniel	Communication 1, the Internet in a Day, day 1 [pdf]		Tanenbaum 4.1
Tue 09/04	daniel	Communication 2, the Internet in a Day, day 2 [pdf]
Wed 09/05	TAs	P0 Recitation (Wean 7500) [pdf]
Thu 09/06	yuvraj	Consistency - Classical synchronization + Go-style concurrency [pdf] [ppt]	Chapter on Condition Variables from the Wisconsin OS book , for more information. Rob Pike - GO Concurrency Patterns	Kesden concurrency notes
Tue 09/11	daniel	Time and Synchronization [pdf]	Recent research on time sync protocols (2018) HUYGENS (PDF)	Tanenbaum 6.1-6.2
Thu 09/13	yuvraj	Remote Procedure Calls [pdf] [ppt]		Tanenbaum 4.2
Tue 09/18	yuvraj	Distributed Filesystems [pdf] [ppt]	See also the book chapters on AFS and NFS from the Wisconsin OS book.
Wed 09/19	TAs	P1 Recitation (Wean 7500) [pdf] [ppt]
Thu 09/20	yuvraj	Distributed Filesystems 2 - AFS, Coda, LBFS, current DFSs [pdf] [ppt]		CODA paper. LBFS paper (read first 6 pages)
Tue 09/25	daniel	Distributed Mutual Exclusion [pdf]		Tanenbaum 6.3-6.4
Thu 09/27	yuvraj	Concurrency Control [pdf] [pptx]		Tanenbaum 8.1, 8.5
Tue 10/02	yuvraj	Logging and Crash Recovery [pdf] [pptx]	Wikipedia Algorithms for Recovery and Isolation.	Tanenbaum 8.1, 8.6
Wed 10/03	TAs	P1 Part B Recitation (Wean 7500) [pdf] [pptx]
Thu 10/04	yuvraj	Distributed Replication [pdf] [pptx]	Further reading for PAXOS. Also check out the RAFT consensus algorithm and a nice Vizualization of how it works!	Tanenbaum Ch7 (p364-p370, p398-p401), Tanenbaum 8.2, Paxos Made Simple Paper
Tue 10/09	freddie and dohyun	Fault Tolerance & RAID [pdf]	See also the book chapter from the Wisconsin book.
Thu 10/11	daniel	Distributed databases (case study), Spanner [pdf]	paper, recent blog post (9/21/18) , hacker news discussion
Tue 10/16	yuvraj & daniel	First Midterm Review [pdf]
Thu 10/18		FIRST MIDTERM EXAM	During class time: 10.30am to 11.50am (please come 5 minutes early and plan to leave around noon). In GHC 4401.
Tue 10/23	daniel	Data center storage (GFS / HDFS) [pdf]	Read Sections 2.3-2.6, 3.1, 3.3, 5.1, 5.2 in the the Google Filesystem paper. Optional GFS follow-up interview.
Wed 10/24	TAs	P2 Recitation (Wean 7500) [pdf]
Thu 10/25	daniel	Data-Intensive Computing and MapReduce/Hadoop [pdf]	Read Sections 3 and 4 in the MapReduce paper, it's pretty readable.
Tue 10/30	daniel	In-memory cluster compute, Spark, Distributed ML [pdf]	Spark/RDD Paper, Helland on Immutability, further refs in slides
Thu 11/01	daniel	Internet Content Delivery [pdf]	Optional readings Akamai paper, consistent hashing theory paper (summary paper), Dropbox Blog Post (10/10/18)	Tanenbaum 5.1-5.5, 7.6
Tue 11/06	Joshua Leners	Guest lecture on datacenter storage systems	Title: Pursuing reliability in storage at Two Sigma, or how I learned to stop worrying and delete 25 PB of data
Thu 11/08	daniel	Virtualization [pdf]	See also the book chapter on Virtual Machines from the Wisconsin OS book
Tue 11/13	daniel	Byzantine Fault Tolerance [pdf]	See also an online lecture about BFT by Barbara Liskov, and the PBFT paper. Optional (fun) read James' Saddest Moment	Tanenbaum pages 449 - 460
Wed 11/14	TAs	P3 Recitation (Wean 7500) [pdf]
Thu 11/15	Dave Andersen	P2P networks, distributed ledgers, and blockchains [txt]	Lecture by Prof. Dave Andersen, from CMU!
Tue 11/20		No Class, Early Thanksgiving
Thu 11/22		No Class, Thanksgiving
Tue 11/27	yuvraj	Security Protocols [pdf] [pptx]	See wikipedia entry for needham-schroeder and wikipedia entry for Diffie-Hellman.	Tanenbaum 9.1-9.3
Thu 11/29	yuvraj	Security II, Case Study - Anonymous Routing and TOR [pdf] [pptx]
Tue 12/04	yuvraj & daniel	Second Midterm Review [pdf]
Thu 12/06		SECOND MIDTERM EXAM	During class time: 10.30am to 11.50am (please come 5 minutes early and plan to leave around noon). In the McConomy Auditorium.