Class materials

  1. Introduction, the "Too Much Milk" problem, the "Coordinated Attack" problem
  2. Mutual exclusion using reads and writes: algorithms and lower bounds
    Accompanying proofs:
    Correctness proofs for mutual exclusion algorithm
    space lower bounds
    Lamport's paper on fast path mutual exclusion (not part of mandatory course materials)
  3. Leader election in rings
    Accompanying proofs
  4. Linearizablility, wait-freedom and register simulations
    Accompanying proofs:
    multi-valued simulation proofs
    multi-reader simulation proofs
  5. Lock-free stack algorithms
  6. Consensus and Herlihy's wait-free hierarchy:
    Accompanying proofs
  7. Atomic Snapshot and the Renaming Problem:
    Algorithm correctness
    Correctness proof for wait-free renaming
  8. Max registers and counters in polylogarithmic time (a presentation by Keren Censor-Hillel)
  9. Local-spin algorithms
  10. Randomized local-spin mutual exclusion
  11. Transactional memory
    Dynamic Software Transactional Memory
    Scheduling memory transactions
    Hardware transactional memory
    An interesting article about IMB's BlueGene/Q support of transactional memory
  12. Concurrent counters: software combining (based on a presentation accompanying the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit.)
  13. Memory-contention lower bounds for counters and other objects
    Accompanying proofs