The Parallel Batch-Dynamic Model with Asynchronous Reads
summary
Introduces a method that adds asynchronous linearizable reads to a parallel batch‑dynamic model by recording and traversing an explicit dependency graph of updates so reads wait only for dependencies they truly need. Applies the technique to a parallel level data structure for k‑core decomposition, preserves atomic per‑update semantics, and keeps reads largely lock‑free. On real graphs with batches up to 10^6 updates, read latency drops ~10^5× versus synchronized reads, stays within 3.2× of naïve non‑sync, throughput within 1.4×, and error within 1.15× of sync.
AI-written summary · about
chapters (9)
- 0:00Batch-dynamic model intro
- 2:55Dynamic graph model variants
- 6:50Motivation for async reads
- 13:15Parallel batch-dynamic model
- 20:28Case study: k-core decomposition
- 28:42Challenges of async reads
- 36:36Dependency graph for linearizable reads
- 38:28Experimental results
- 42:25Ongoing work
related talks
19mConcurrent Data Structures Made Easy
51mThe Need for Async
01h 06m“How to make your data structures wait-free for reads"
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
48m“Is Parallel Programming still hard? PART 2 of 2”
36mThe Good, The Bad, and the Ugly: A Journey from this synchronized to Asynchronous Code
35mPredictable Latency
49mStriving to Make Things Simple and Fast