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:

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:

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
Wed 08/30 daniel Introduction
[pdf]
1.1, 1.2
Fri 09/01 daniel Communication, the Internet in a Day
[pdf]
4.1
Sat 09/02 daniel Communication Optional Recitation
[pdf] [pptx]
Computer Networks - A Systems Approach, by Larry Peterson and Bruce Davie
Tue 09/05 Go! and P0 overview
Wed 09/06 daniel Consistency - Classical synchronization + Go-style concurrency
[pdf]
Kesden concurrency notes
The Little Book of Semaphores
Fri 09/08 No Class
Wed 09/13 daniel Time and Synchronization
[pdf] [pptx]
Tanenbaum 6.1-6.2
Fri 09/15 daniel Remote Procedure Calls
[pdf] [pptx]
Tanenbaum 4.2-4.3
Wed 09/20 daniel Distributed Filesystems 1 - NFS and AFS
[pdf] [pptx]
See also the book chapters on AFS and NFS from the Wisconsin OS book.
Fri 09/22 daniel Distributed Filesystems 2 - Coda, LBFS, Dropbox
[pdf] [ppt]
About CODA
LBFS Paper
Wed 09/27 daniel Distributed Mutual Exclusion
[pdf] [pptx]
Tanenbaum 6.3-6.4
Fri 09/29 daniel Concurrency Control
[pdf] [pptx]
Tanenbaum 8.1, 8.5
Wed 10/04 daniel Logging and Crash Recovery
[pdf]
See updated slides 19 and 20 for unanswered question from lecture. Also take a look at Wikipedia Algorithms for Recovery and Isolation. Tanenbaum 8.1, 8.2, 8.6
Fri 10/06 daniel Distributed Replication
[pdf] [pptx]
Further reading for PAXOS. Also check out the RAFT consensus algorithm and a nice Visualization of how it works! Tanenbaum 7.2.2 (p364-p370), 7.5.2, Tanenbaum 8.2, Paxos Made Simple Paper
Wed 10/11 daniel Fault Tolerance & RAID
[pdf] [pptx]
See also the book chapter from the Wisconsin book.
Fri 10/13 daniel DNS
[pdf] [pptx]
Cheat sheet on using and interpreting dig
Sun 10/15 srini & daniel Midterm Review (10am DH 2315)
[pdf] [pptx]
Mon 10/16 MIDTERM EXAM (6pm DH 2210)
Wed 10/18 No Class
Fri 10/20 No Class
Wed 10/25 daniel Data-Intensive Computing and MapReduce/Hadoop
[pdf] [pptx]
For more info, see the MapReduce paper, it's pretty readable. You might want to examine the Hadoop code for Word Count and Matrix multiplication.
Fri 10/27 daniel GFS / HDFS
[pdf]
Read the Google Filesystem. Optional GFS follow-up interview.
Wed 11/01 daniel Spanner, Naming, Hashes
[pdf]
Read the OSDI Spanner paper (as only parts are covered in the lecture), some background on Dyn DNS attack from last year , the paper that termed consistent hashing
Fri 11/03 daniel Content Delivery Networks
[pdf]
Tanenbaum 2.3
Wed 11/08 daniel Peer-to-Peer and Blockchains
[pdf]
Read Sections 2 and 3 in the Untangling Blockain Paper. Mysterious beginnings of bitcoin
Fri 11/10 No Class , CMU anniversary celebration
Wed 11/15 daniel Spark and Distributed Machine Learning
[pdf]
RDD Paper (see footnote 2 (page 2) for discussion of RDD immutability), also take a look at the many references in the slides
Fri 11/17 daniel and daehyeok Virtualization
[pdf]
See also the book chapter on Virtual Machines from the Wisconsin OS book
Fri 11/17 daniel Byzantine Fault Tolerance
[pdf]
Please read Tanenbaum Consensus in faulty systems with arbitrary failures (page 449f) and and Example Practical Byzantine Fault Tolerance (page 456f). Practical BFT corresponds to the Async BFT discussed in the lecture. Also see Barbara Liskov's online lecture on BFT, and the PBFT paper. Tanenbaum pages 449 - 460
Wed 11/22 No Class, Early Thanksgiving
Fri 11/24 No Class, Thanksgiving
Wed 11/29 yuvraj Security Protocols
See wikipedia entry for needham-schroeder and wikipedia entry for Diffie-Hellman. Tanenbaum 9.1-9.2, 9.4.1
Fri 12/01 daniel Security II, Case Study - Anonymous Routing and TOR
Wed 12/06 daniel Final Review (to be rescheduled)
Fri 12/08 No Class, Early Exam Break
Sun 12/17 FINAL EXAM - time 5:30pm - room TBD

As mentioned in class about the link to Amazon: David Andersen is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to amazon.com.


Last updated: 2017-11-18 12:19:46 -0500 [validate xhtml]