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