Implementing wait-free space bounded shared memory primitives on concurrent systems
summary
Describes a transformation that turns many sequentially writable objects plus basic registers into a single concurrently writable object that is wait-free, preserves the original object’s step complexity with constant step overhead, and uses n^2 space (n processes); implementing a k-word register costs k·n^2 single-word registers, there is a trivial lower bound of n, and prior general techniques are only lock-free. The construction uses announce arrays / hazard-like reclamation; those reclaimers break strong linearizability, but a recent PODC construction achieves strongly linearizable LL/SC.
AI-written summary · about
chapters (8)
- 0:00Wait-free shared memory primitives
- 1:43Linearizability and progress conditions
- 6:31Memory reclamation overview
- 13:24Unbounded memory with global pointer
- 19:58Space bounds with per-process objects
- 26:48Strong linearizability for randomized algorithms
- 31:05Conclusion and open questions
- 32:08Q&A: Hazard pointers
related talks
01h 06m“How to make your data structures wait-free for reads"
21mEvery Data Structure Deserves Lock-Free Memory Reclamation
19mConcurrent Mutation must go
30mA Tale of Shared Memory Concurrency in Programming Languages
51mMemory Model: Get your shared data under control
21mA Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation
55m“A lock-free concurrency toolkit for deferred reclamation and optimistic speculation"
01h 15mWait-free memory reclamation and data structures