COSC 546 - Distributed Algorithms

Spring 2016

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 11:00 to 12:15

Intercultural Center, 205B

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 large-scale systems, however, came a new algorithmic scenario: multiple computing devices, connected by 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 setting where time complexity is often obvious or not relevant, but proving that an algorithm works is difficult. There is less algebra deployed in analyzing distributed algorithms, 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 once quirky corner of computer science has recently become crucial as more and more of the infrastructure supporting our current digital age leverage big distributed systems tamed by smart distributed algorithms. For companies like Facebook, Google, and Amazon, which depend on somehow coaxing hundreds of thousands of machines spread over massive data centers to work well together, this subject has become a necessity. (Which makes this topic particularly good to know for those interested in entering the technology job market!)

Who Can Take This Course

This course is listed as a graduate elective and therefore its primary audience is computer science masters and doctoral students. The material, however, is also suitable for senior undergraduate computer science majors interested in graduate study or pursuing jobs at competitive technology companies. If you are an undergraduate interested in this course, please contact me.

Course Structure

The course is divided into three parts. The first two parts cover the fundamentals of designing and analyzing distributed algorithms. The third part covers a selection of more recent results in the study of distributed algorithms.

There will be three non-cumulative exams for the course, one for each of the three parts. There are no problem sets in this course (though I am happy to assign and discuss practice exercises by student request). This course focuses on the design and analysis of distributed algorithms from a theoretical perspective, not their implementation. There are, therefore, no programming assignments.


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 draw from this textbook, though I will also cover material not in this book.


Grades in the course will be based on your three exams. Class attendance is highly recommended as I will cover material not included in the textbook, as well as cover material from the book in a new manner.

Course Logistics

Office Hours

I hold regular office hours in my office at 334 Saint Mary's Hall from 12:30 to 1:30 on Tuesday and Thursday.


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


Below is the tentative schedule for the course. I will continue to modify it as the semester progresses. The readings column lists the chapters from the Lynch textbook that best correspond to the lecture's material. As noted, however, not all of the material covered is in the textbook, and I will cover some of the textbook material in a new manner.

Note: The syllabus for the third part of the semester will be set during the semester.

Class NumberDateDescription Readings
Part 1: Synchronous Networks
11/14Introduction to distributed algorithms; course overview 
21/19Leader election in rings: basic algorithms and impossibilities. 3.1 - 3.3
31/21Leader election in rings: better algorithms.3.4 - 3.5
41/26Solving problems in general network graphs: leader election, breadth-first search, and shortest path.4.1 - 4.3
51/28Minimum spanning trees.
62/2Impossibility of consensus with link failures, algorithms for consensus with process failures.5.1, 6.1 - 6.2
72/4A lower bound on consensus with process failures.Keidar and Rajsbaum, 2003
82/9Set-consensus and distributed commit.7.1, 7.3
92/11Byzantine consensus: algorithms and impossibilities.
102/16Exam review. 
112/18Exam #1.
Part 2: Asynchronous Shared Memory and Network Systems
122/23Shared memory model and mutual exclusion with registers.
10.1 - 10.3
132/25Improved mutual exclusion with registers.10.5, 10.7
143/1The dining philosophers problem.11.1 - 11.3
153/3The impossibility of consensus with process failures.
 3/8No Class: Spring Break 
 3/10No Class: Spring Break 
163/15Asynchronous network model: solving leader election in rings and building spanning trees.15.1, 15.3
173/17Connecting the asynchronous shared memory and network models17.1 - 17.2
183/22Connecting the asynchronous shared memory and network models (cont); the PAXOS consensus algorithm.17.1 - 17.2; Lamport 2001
 3/24No Class: Easter Break 
193/29Partially synchronous systems: basic results for mututal exclusion and consensus.
24.1 - 24.2, 25.1 - 25.3
203/31Exam review. 
214/5Exam #2.
Part 3: Recent and Advanced Results
224/7The wait-free hierarchy.Herlihy 1991
234/12Random rumor spreading.Giakkoupis 2011
244/14Consensus with limited network information.Newport 2014
254/19Dynamic networks.Kuhn, Lynch, and Oshman 2010
264/21Radio networks.Bar-Yehuda, Goldreich, and Itai 1992
274/26Lower bound for radio networks. Newport 2013
284/28Overflow; Exam review. 
  Final examination (date and location to be announced)