Topics

1. Introduction
   • Muddy Children Puzzle
   • Coordinated Attack Problem
   • The Consensus Problem

2. Mutual Exclusion
   • Peterson's Algorithm
   • FCFS and Lamport's Bakery Algorithm
   • Adaptivity and Local Spinning Properties
   • Anderson's Algorithm
   • MCS Algorithm
   • Achieving process priorities
   • Abortable mutual exclusion

3. Nonblocking Algorithms
   • Atomicity/Linearizability
   • Liveness Conditions: Wait-Free, Non-Blocking, Obstruction-Free conditions
   • Consensus Hierarchy
   • Some wait-free algorithms: snapshots and f-arrays
   • Universal wait-free construction
   • Atomic Transactions
   • Implementing Lock-based and Obstruction-free Transactions

4. Message Passing Algorithms
   • Logical clocks
   • Chandy and Lamport's Snapshot Algorithm
   • Byzantine Generals Problem
   • Fischer, Lynch and Paterson's Result on the Impossibility of Consensus
   • Failure Detectors