We will study some of the key building blocks – such as synchronization primitives, group communication protocols, and replication techniques – that form the foundation of modern distributed systems, such as cloud-computing platforms or the Internet. We will also look at some real-world examples of distributed systems, such as GFS, MapReduce, Spark, and Dynamo, and we will gain some hands-on experience with building and running distributed systems.
CIS 505 is one of the core courses in the MSE and EMBS programs, and its final exam qualifies as one of the WPE-I exams in the PhD program.
Instructor:
Linh Thi Xuan Phan
Office hours: Wednesdays 1:30-2:30pm (Levine 576)
When and where:
Mondays/Wednesdays 12:00-1:30pm, Skirkanich Auditorium
Teaching assistants:
| Robert Gifford Office hours: Mondays 10:00-11:00am Location: Levine 5th floor bump space |
Saket Karve Office hours: Mondays 3:00-4:00pm Location: GRW 5th floor bump space |
| Garvit Khandelwal Office hours: Tuesdays 2:00-3:00pm Location: Levine 5th floor bump space |
Varad Deshpande Office hours: Tuesdays 3:00-4:00pm Location: Levine 6th floor bump space |
| Akhilesh Gupta Office hours: Wednesdays 4:00-5:00pm Location: Levine 5th floor bump space |
Waley Zhang Office hours: Wednesdays 5:00-6:00pm Location: Levine 6th floor bump space |
| Michael Henehan Office hours: Thursdays 3:00-4:00pm Location: Levine 5th floor bump space |
Max Demoulin Office hours: Thursdays 4:00-5:00pm Location: Levine 6th floor bump space |
| Neeraj Gandhi Office hours: Fridays 9:00-10:00am Location: Levine 6th floor bump space |
Chris Fischer Office hours: Fridays 11:00-12:00pm Location: Levine 5th floor bump space |
Course textbook:
Distributed Systems: Principles and Paradigms, 3rd edition (by M. van Steen and A. Tanenbaum; ISBN 978-1543057386).
You can get a digital version of this book for free; hardcopies are available, e.g., from Amazon.
Additional material will be drawn from selected research publications.
Prerequisites:
Either undergraduate networking or operating systems is required. You should also be comfortable with programming in C/C++.
Workload:
The course will involve three substantial programming assignments, a group project,
a midterm, and a final examination.
Grading:
Your letter grade will be based on the programming assignments (30%), the group project (25%), the
midterm exam (15%), the final exam (25%), and your participation (5%).
We will be using Piazza for all course-related discussions.
Homework assignments and project are available for download; you can submit your solution online. If necessary, you can request an extension for your homeworks.
 Garvit Gupta, Shiva Suri, Anant Maheshwari and Sahana Vijaya Prasad |
 Example services of the winning project. |
The Spring 2018 PennCloud Award went to Garvit Gupta, Anant Maheshwari, Sahana Vijaya Prasad, and Shiva Suri for the overall best final project. The team presented a solid design of a fault-tolerant cloud platform with strong consistency, qourum-based replication, and efficient checkpointing and recovery. The platform provides a diverse set of services with multiple useful features, such as a webmail service that supports multiple users, mail folders, sorting and labeling; a storage service that supports uploading and downloading of files in any format; and a user-friendly admin console. Besides these core functionalities, the platform also offers users a novel and beautifully-designed tic-tac-toe game that is built on top of group communication.
You can read more about winners and their projects in the CIS505 Hall of Fame.
| Date | Topic | Details | Reading | Remarks |
|---|---|---|---|---|
| Aug 28 | Introduction [.pdf] | Course overview Policies |
Chapter 1 | |
| Sep 2 | Labor Day - No class | HW0 | ||
| Sep 4 | Processes and threads [.pdf] | Basic concepts The UNIX model Implementation in the kernel |
Chapter 3.1 (Sections 1+2) | HW0 due (on 9/6); HW1 |
| Sep 9 | System calls [.pdf] | System calls The file API Kernel entry/exit |
||
| Sep 11+16 | Concurrency control [.pdf] | Synchronization primitives Race conditions, critical sections Deadlock and starvation |
||
| Sep 18 | Synchronization [.pdf] | Semaphores Classical synchronization problems Monitors and condition variables |
||
| Sep 23 | Communication [.pdf] | Sockets Socket programming Handling multiple connections |
Chapters 4.1+4.3 + 3.1 (Section 3) | HW1 due (on 09/20); HW2 |
| Sep 25 | Remote Procedure Calls [.pdf] | Programming model Stub code; marshalling; binding Handling failures |
Chapters 4.2+8.3 | |
| Sep 30 | Naming [.pdf] | Kinds of names; name spaces The Domain Name System LDAP |
Chapter 5 | HW2MS1 due (on 10/01) |
| Oct 2+7 | Clock synchronization [.pdf] | Logical clocks Distributed mutual exclusion NTP |
Chapters 6.1–6.3 | |
| Oct 7 | Last day to drop | |||
| Oct 9 | Distributed coordination [.pdf]
Midterm review |
Distributed mutual exclusion Leader election Bully algorithm; token ring |
Chapter 6.4 | |
| Oct 10–13 | Fall break | |||
| Oct 14 | Class is canceled - Linh is at ESWeek | HW2MS2+3 due | ||
| Oct 16 | Midterm | The midterm will cover topics from the first lecture | ||
| Oct 21 | Group communication [.pdf] | Reliable multicast IP multicast FIFO, causal and total ordering |
Chapter 8.4 | |
| Oct 23 | Algorithms for FIFO, causal and total ordering | HW3 | ||
| Oct 28 | Replication [.pdf] | Primary/backup protocols Quorum protocols Sequential and causal consistency Client-centric models |
Chapter 7 | Project |
| Oct 30 | Bigtable and Project [.pdf] | Bigtable case study Project overview |
[Bigtable] | |
| Nov 4 | Fault tolerance [.pdf] | 2PC and 3PC Logging and recovery Chandy-Lamport algorithm |
Chapters 8.5+8.6; [Chandy-Lamport] | |
| Nov 4 | Last day to withdraw | |||
| Nov 6 | State-machine replication [.pdf] | Failure models The Consensus problem Paxos |
Chapters 8.1+8.2; [Paxos] | HW3 due (on 11/8) |
| Nov 11 | Non-crash Fault Tolerance [.pdf] | The Byzantine Generals problem Impossibility results Solutions |
[BFT] | Project proposal due |
| Nov 13 | ||||
| Nov 18 | Distributed file systems [.pdf] | NFS Coda Disconnected operation |
Chapter 2.4.2; [Coda] | Nov 20 | Google File System [.pdf] | Google cluster architecture Reading and writing in GFS Consistency and fault tolerance |
[Cluster] [GFS] |
| Nov 25 | MapReduce [.pdf] | MapReduce programming model System architecture |
[MapReduce] | |
| Nov 27 | Thanksgiving break - no class (Friday schedule) | |||
| Dec 2 | Spark [.pdf] | Differences to MapReduce RDDs Case study: PageRank |
[Spark] | |
| Dec 4+9 | DHTs and Dynamo Exam review [.pdf] |
Distributed hash tables The CAP dilemma Amazon Dynamo |
[Dynamo] | |
| Dec 10–11 | Reading days | |||
| Dec 12 | Final Exam (12-2pm) | The final exam will cover all topics studied in the entire semester | ||
| Dec 13–Dec 19 | Project demos and reports | |||