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