The Complexity of Testing Message-Passing Concurrency
summary
Characterizes channel-consistency as a parameterized complexity landscape: consistency checking is NP-hard even for single-valued or capacity‑one channels, and hardness persists across small numbers of threads, channels, and capacities; provides matching upper bounds via a frontier-graph algorithm whose running time is exponential in the number of threads but polynomial when threads or capacities are fixed; implements the algorithm, evaluates on 103 Go instances, and shows it scales to ~1M events and beats a constraint‑solving baseline.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:03Concurrency testing matters
- 3:35Predictive analysis and model checking
- 7:32Channel consistency problem
- 14:37Complexity results and findings
- 17:27Channels harder than registers
- 19:15Algorithm for VCH problem
- 22:10Communication topologies
- 22:52Evaluation and performance
- 24:17Summary
related talks
36mConcurrent ML - The One That Got Away
54mDesigning for Concurrency Using Message Passing in C++
35mCommunicating Sequential Processes
20mHow Hard is Weak-Memory Testing?
01h 16mDesigning for C++ Concurrency Using Message Passing
01h 35mThinking Outside the Synchronisation Quadrant
20mCoarser Equivalences for Causal Concurrency
39mLet's talk concurrency