Concurrent Algorithms & Data Structures

Background

Most computer applications today run on concurrent platforms: multicore architectures, distributed databases, geographically distributed servers. The algorithms and data structures designed over the years for sequential programs must therefore be extended to the concurrent setting. This course studies how that is done for basic data structures such as sets, stacks and queues, together with the algorithms that manipulate them (insertion, deletion and membership checking), and how to reason about their correctness and efficiency.

Lectures

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

Topics covered

• Concurrent programs
• Concurrent data structures
• Abstract data types
• Sets
• Stacks
• Queues
• Concurrent histories
• Sequential consistency
• Linearizability
• Coarse-grained synchronization
• Fine-grained synchronization
• Optimistic algorithms
• Lazy algorithms
• Lock-free algorithms
• The ABA problem
• Atomic operations