Advanced Topics in Distributed and Concurrent Algorithms
Com S 611 Spring 2015


This course will cover algorithms and lower bound results for concurrent objects and synchronization. Given the spread of multiprocessor architectures, it is important to understand how to make computing more efficient by exploiting parallelism. To do this, proper synchronization and communication is essential among the processors that are working together on a common task. These multiprocessors will communicate through shared memory. We will study formally the types of coordination that are needed when processors are taking steps concurrently. We will see that there are inherent limitations on parallelism of certain events. One way to make sure certain events do not overlap is to use a mutual exclusion lock. The negative of this is that it requires waiting; a processor will need to wait until another processor completes its steps. To counter this, we introduce the wait-free and lock-free models of computation. Wait-free algorithms make progress even if only one processor is taking steps. However, these are harder to reason about. This study will lead to both algorithms, as well as impossibility results and lower bounds.

There is no textbook for the courseMaterial will be taken from current papers. The course grade will be based on taking scribe notes, reading papers and producing written summaries, and presenting a paper in class. There will be no exams.

As a pre-requisite for the course, you will be expected to be familiar with the basic concepts behind the design and analysis of sequential algorithms. This familiarity can be obtained from Com S 511 and, to a lesser extent, from Com S 311. Also, you should be comfortable with reasoning through and writing mathematical proofs. Lower bound proofs and impossibility proofs in distributed computing sometimes have the same style as the proofs done in a Theory of Computation course like Com S 531, though we will see differences in the way we reason about single processor sequential computation and multiprocessor concurrent computation. A background in parallel or distributed systems would be helpful to appreciate the results and applications of the course material, but is not essential.


We will start by covering the following topics, focussing on theoretical results. To provide background, we will also prove some fundamental results in distributed computing, as they relate to the topics studied.

  • Mutual Exclusion
  • Memory Consistency Conditions
  • Wait-Free Register Implementation
  • Concurrent Objects and Synchronization in Shared Memory systems
  • Fault-tolerant and Randomized Data Structures
  • Wait-Free Hierarchy
  • Lock-Free Computations
  • Distributed Storage
  • Security Issues in Distributed Systems

Your grade will be based on your performance on scribe notes, assignments and paper summaries, and your class presentations.

  • Annotated Scribe Notes need to be written in latex. They should be complete and go beyond just copying what was presented. The scribe should include interesting points made in the class discussion. Also, clarify any confusing points. You may also include your own perspective or critique on the paper or topic presented. You may asked to complete and provide details to a proof that was started or summarized in the lecture. A first draft of the notes should be ready within a few days of the lecture.
  • Presentations will involve presenting papers on one or two of the topics that we cover in class. These student presentations will be at the end of the semester.
  • The final paper should go into depth on one of the topics related to the material covered. It can either be a survey paper or can include original research results.

Tentative Weights of Graded Materials

  • 40% -- Scribe Notes
  • 25% -- Presentations
  • 25% -- Final Paper
  • 10% -- Class Participation