- Introduction - Synchronization
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
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 - 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
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 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
Safe Memory Reclamation
Hazard pointers, access hazard, ABA hazard, application of hazard pointers.
Definition of a barrier, barrier Implementations, sense-reversing barrier, combining tree barrier, static tree barrier, termination detection barriers.