/
Concurrent Programming
Concurrent Programming
August – November 2015
Administrative Details
- Evaluation
- Resources
- The Art of Multiprocessor Programming, Maurice Herlihy and Nir Shavit (Morgan Kaufmann)
- Submit all assignments on Moodle only. Further instructions will be given as part of the assignments.
Course Plan
- Introduction to concurrency and motivating examples
- Mutual exclusion: Algorithms and lower bounds
- Concurrent objects: Correctness notions like sequential consistency, linearizability, etc. Progress notions: deadlock-free, starvation-free, lock-free, wait-free, etc.
- Register types: MRSW, SRSW etc. Various register simulations
- Consensus problem: consensus number of various concurrent objects, upper and lower bounds
- Spin locks: Test-and-Set locks, CLH lock, MCS lock, multi-core considerations
- Monitors
- Concurrent data structures: General considerations
- Linked lists
- Queues and the ABA problem
- Stacks and the elimination technique
- Counting and Sorting Networks
- Heaps, skip lists etc. (if time permits)
- Transactional Memory basics
- Some distibuted algorithms (if time permits)
Assignments
Lectures
Resources