COSC 242 - Algorithms for Distributed Systems

Fall 2013

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 3:30 - 4:45

Reiss 281

Course Overview


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.)

Course Structure

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%.

Course Logistics

Office Hours

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.

Problem Sets

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).

Academic Integrity

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 NumberDateDescription Readings
Part 1: Synchronous Networks
18/29Introduction to distributed algorithms; course overview 
29/3Leader election in rings: basic algorithms and impossibilities. 3.1 - 3.3
39/5Leader election in rings: better algorithms.3.4 - 3.5
49/10Solving problems in general network graphs: leader election, breadth-first search, and shortest path.4.1 - 4.3
59/12Minimum spanning trees.
Homework #1 handed out.
69/17Impossibility of consensus with link failures, algorithms for consensus with process failures.5.1, 6.1 - 6.2
79/19A lower bound on consensus with process failures.Keidar and Rajsbaum, 2003.
89/24Set-consensus and distributed commit.7.1, 7.3
99/26Byzantine consensus: algorithms and impossibilities.
Homework #1 due.
1010/1Exam review. 
1110/3Exam #1.
Homework #2 handed out.
Part 2: Asynchronous Shared Memory and Network Systems
1210/8Shared memory model and mutual exclusion with registers.
10.1 - 10.3
1310/10Improved mutual exclusion with registers.10.5, 10.7
1410/15The dining philosophers problem.11.1 - 11.3
1510/17The impossibility of consensus with process failures.
Homework #2 due.
Homework #3 handed out.
1610/22Asynchronous network model: solving leader election in rings and building spanning trees.15.1, 15.3
1710/24Connecting the asynchronous shared memory and network models.17.1 - 17.2
1810/29The PAXOS consensus algorithm and reliable replicated state.Lamport, 2001
1910/31Partially synchronous systems: basic results for mututal exclusion and consensus.
Homework #3 due.
24.1 - 24.2, 25.1 - 25.3
2011/5Exam review. (Withdraw Deadline) 
2111/7Exam #2.
Homework #4 handed out.
Part 3: Real Systems and Recent Results
2211/12Google's File System 
 11/14No Class 
2311/19Practical Byzantine Fault-Tolerance 
2411/21Akami's Network Caches.
Homework #4 due.
2511/26Distributed Algorithms for Peer-to-Peer Networks 
 11/28No Class: Thanksgiving Break 
2612/3Distributed Algorithms for Social Networks 
2712/5Distributed Algorithms for Wireless Networks 
 12/14Final examination (the exam is from 12:30 to 2:30 pm in ICC 207a)