Most computer applications operate nowadays on concurrent platforms, e.g., multicore architectures, distributed databases, and geographically distributed servers. This means that all the algorithms and data structures that have along the years have been designed for sequential programs must be extended to the concurrent setting. In this course, we study how this is done in the case of basic data structures such as sets, stacks, and queues. We will also study algorithms that manipulate data structures, such as insertion, deletion, and membership checking. Furthermore, we will reason about the correctness and efficiency of these algorithms.

Concrete topics: concurrent programs, concurrent data structures, sets, stacks, queues, sequential consistency, linearizability, coarse-grained synchronization fine-grained synchronization, optimistic algorithms, lazy algorithms, lock-free algorithms, the ABA problem, and atomic operations.

• Lectures and Tutorials.
• Project work. The project will consist of implementing some of the algorithms discussed in the class.

• Written exam.
• Weekly assignments.
• Project work.

• Course suitable both for PhD and MSc students.
• Primary knowledge corresponding to three years of an undergraduate program in computer science.

• Lecture 1: Introduction. keynote. pdf.
• Lecture 2: Abstract Data Types. keynote. pdf.
• Lecture 3: Sequential Programs. keynote. pdf.
• Lecture 4: Histories. keynote. pdf.
• Lecture 5: Linearizability. keynote. pdf.
• Lecture 6: Coarse-Grained Sets. keynote. pdf.
• Lecture 7: Fine-Grained Sets. keynote. pdf.
• Lecture 8: Optimistic Synchronization. keynote. pdf.
• Lecture 9: Lazy Synchronization. keynote. pdf.
• Lecture 10: Lazy Synchronization (ctd). keynote. pdf.
• Lecture 11: The Treiber Stack Algorithm. keynote. pdf.
• Lecture 12: The Michael-Scott Algorithm. keynote. pdf.

• Lecture 1(1). Lecture 1(2).
• Lecture 2(1). Lecture 2(2).
• Lecture 3(1). Lecture 3(2).
• Lecture 4(1). Lecture 4(2).
• Lecture 5(1). Lecture 5(2).
• Lecture 6(1). Lecture 6(2).
• Lecture 7(1). Lecture 7(2).
• Lecture 8(1). Lecture 8(2).
• Lecture 9(1). Lecture 9(2).
• Lecture 10(1). Lecture 10(2).
• Lecture 11(1). Lecture 11(2).
• Lecture 12(1). Lecture 12(2).

• The Art of Multiprocessor Programming. Maurice Herlihy and Nir Shavit..

• Parosh Aziz Abdulla.