Traditional computer science emphasizes the design and analysis of sequential algorithms, which are meant to be executed on a single computing device. With the rise of network technology, however, came a new algorithmic scenario: multiple computing devices, connected by some sort of communication channels or shared objects, that must work together to solve problems. These distributed systems require distributed algorithms.
The world of distributed algorithms is quite different than the world of sequential algorithms. It is a world where the time complexity is often obvious but proving that an algorithm works is difficult. There is less algebra in the distributed setting, but more mind-bending logic arguments. Distributed algorithm theorists almost never utter the phrases "master theorem" or "dynamic programming," but instead talk about "byzantine adversaries" and "indistinguishability." Perhaps most interesting, in distributed computing, many problems that seem easy turn out to be impossible to solve, while some difficult sounding puzzles yield simple solutions.
This is a quirky but important corner of computer science that turns out to be a lot of fun to explore. (It is also, one must add, a good world to know about when entering the job market.)
The first two thirds of this course will teach you the fundamentals of designing and analyzing distributed algorithms. The last third of the course focuses on real distributed systems, leveraging your knowledge from the preceding lectures to help you dissect and understand the strategies that keep systems like Google's data centers or popular peer-to-peer networks operational.
There will be three non-cumulative exams for the course, one for each third. There will also be four problem sets covering the first two parts of the course. You will have two weeks for each problem set.
There will by no programming in this course. As with the standard algorithms course, it is primarily theoretical in nature.
The required textbook for this course is Distributed Algorithms, Nancy Lynch, 1996. Most of the topics covered in the first two thirds of this course, as well as some problem set problems, will be drawn from this textbook.
Grades in the course will be based on the problem sets, exams, and participation. The participation grade will be based on your attendance and involvement in class. If you show up to class, pay attention, and ask questions when stuck (either in class, or after class), you will get full participation points.
Your final grade will be based on the percentage of total available points you earned throughout the semester. The mapping of final percentage to letter grades is not fixed in advance, but instead something I will define as I get a better feel for the relative difficulty of the assigned material. When in doubt about how well you are doing: ask me.
I will assign the point value of different assignments such that the exams combined represent roughly 60% of available points, the problem sets 35%, and participation the final 5%.
I hold regular office hours from 1:00 to 2:30 pm on Thursdays, in my office at 342 A Saint Mary's Hall. If this time conflicts with your class schedule, let me know, and we can arrange alternate meetings as needed. Beware that my office number might change at some point during this semester.
To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, I prefer that you bring them to office hours. Use e-mail only when the above two options are not applicable.
The following rules will help keep the problem set submission and grading process running smoothly:
There will be three exams in the course: two midterms and a final. The exams are non-cumulative (that is, each covers only the new material since the last exam).
I take academic integrity seriously. To repeat the problem set instructions from above: You must work alone on problem sets. You may only discuss problems with me. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources or talk to other students.
You may not bring any outside material into exams.
You may not reference any problem sets or solutions from similar courses offered at other schools.
When in doubt, ask me what is allowed.
Below is the tentative schedule for the course. I will modify the schedule as needed as the course progresses. Problem sets will be posted below on this schedule as they become available. The readings column lists the chapters from the Lynch textbook that cover the corresponding lecture's material.
Note: The syllabus for the third part of the semester will be set during the semester.
Class Number | Date | Description | Readings |
Part 1: Synchronous Networks | |||
1 | 8/29 | Introduction to distributed algorithms; course overview | |
2 | 9/3 | Leader election in rings: basic algorithms and impossibilities. | 3.1 - 3.3 |
3 | 9/5 | Leader election in rings: better algorithms. | 3.4 - 3.5 |
4 | 9/10 | Solving problems in general network graphs: leader election, breadth-first search, and shortest path. | 4.1 - 4.3 |
5 | 9/12 | Minimum spanning trees. Homework #1 handed out. | 4.4 |
6 | 9/17 | Impossibility of consensus with link failures, algorithms for consensus with process failures. | 5.1, 6.1 - 6.2 |
7 | 9/19 | A lower bound on consensus with process failures. | Keidar and Rajsbaum, 2003. |
8 | 9/24 | Set-consensus and distributed commit. | 7.1, 7.3 |
9 | 9/26 | Byzantine consensus: algorithms and
impossibilities. Homework #1 due. | 6.3 |
10 | 10/1 | Exam review. | |
11 | 10/3 | Exam #1. Homework #2 handed out. | |
Part 2: Asynchronous Shared Memory and Network Systems | |||
12 | 10/8 | Shared memory model and mutual
exclusion with registers. | 10.1 - 10.3 |
13 | 10/10 | Improved mutual exclusion with registers. | 10.5, 10.7 |
14 | 10/15 | The dining philosophers problem. | 11.1 - 11.3 |
15 | 10/17 | The impossibility of consensus with process
failures. Homework #2 due. Homework #3 handed out. | 12.3 |
16 | 10/22 | Asynchronous network model: solving leader election in rings and building spanning trees. | 15.1, 15.3 |
17 | 10/24 | Connecting the asynchronous shared memory and network models. | 17.1 - 17.2 |
18 | 10/29 | The PAXOS consensus algorithm and reliable replicated state. | Lamport, 2001 |
19 | 10/31 | Partially synchronous systems: basic results
for mututal exclusion and consensus. Homework #3 due. | 24.1 - 24.2, 25.1 - 25.3 |
20 | 11/5 | Exam review. (Withdraw Deadline) | |
21 | 11/7 | Exam #2. Homework #4 handed out. | |
Part 3: Real Systems and Recent Results | |||
22 | 11/12 | Google's File System | |
11/14 | No Class | ||
23 | 11/19 | Practical Byzantine Fault-Tolerance | |
24 | 11/21 | Akami's Network Caches. Homework #4 due. | |
25 | 11/26 | Distributed Algorithms for Peer-to-Peer Networks | |
11/28 | No Class: Thanksgiving Break | ||
26 | 12/3 | Distributed Algorithms for Social Networks | |
27 | 12/5 | Distributed Algorithms for Wireless Networks | |
12/14 | Final examination (the exam is from 12:30 to 2:30 pm in ICC 207a) |