Topic outline

  • General

    Collapse all Expand all

  • Introduction - Synchronization

    Definition of a distributed system, difficulties encountered in achieving parallelism, Amdahl's Law, characteristics of concurrent algorithms, modeling a shared memory system.

  • Mutual Exclusion

    The mutual exclusion problem, mutual exclusion (ME) algorithms, Peterson's algorithm, ME algorithm using Single-Writer binary RW registers, ME algorithms for many processes, Tournament ME algorithm, the bakery algorithm, the black-white bakery algorithm, tight space bounds for mutual exclusion using atomic registers, lower bound, the One-Bit algorithm.

  • Spin Locks and Contention

    The TAS and TTAS locks, exponential backoff, queue locks, Anderson's Algorithm - the array-based lock, the CLH lock, the MCS lock, drawbacks of queue locks, the basics of the Combining Technique, CC-Synch, H-Synch.


  • Concurrent Objects - Correctness, Progress and Efficiency

    Concurrent objects, global state predicate evaluation, snapshot object, implementations of snapshots from r/w registers, correctness and termination, wait-freedom, linearizability, histories, locality, linearizable implementations, sequential consistency, the UnboundedSnapshot algorithm.

  • Foundation of Shared Memory: Fault -Tolerant Simulations of read/write objects

    Multi-valued single-writer (SW) single-reader (SR) registers from binary SW SR registers, multi-reader from single-reader registers, multi-writer from single-writer registers.

  • Fault-Tolerant Consensus

    Consensus on a synchronous shared-memory system, modeling message passing systems, impossibility of consensus in asynchronous shared-memory systems.

  • Wait-Free Simulations of Arbitrary Objects

    Wait-free simulations of arbitrary shared objects, example of a FIFO queue, the strong compare & swap primitive, the wait-free hierarchy, universality, a non-blocking universal construction using compare & swap, a non-blocking universal construction using consensus objects, a wait-free universal construction using consensus objects, bounding the memory requirements, handling non-determinism, employing randomized consensus



  • Concurrent Pools

    Definition of concurrent pools, unbounded total queue, unbounded lock-free queue, the ABA problem, dual data structures, unbounded lock-free stack, elimination, the elimination backoff stack, lock-free exchanger, shared lists, linked lists, coarse grained synchronization, fine grained synchronization, optimistic synchronization, lazy synchronization, non-blocking synchronization. 


  • Safe Memory Reclamation

    Hazard pointers, access hazard, ABA hazard, application of hazard pointers.


  • Barriers

    Definition of a barrier, barrier Implementations, sense-reversing barrier, combining tree barrier, static tree barrier, termination detection barriers.