The Complexity of Testing Message-Passing Concurrency
Zheng Shi, Lasse Møldrup, Umang Mathur, Andreas Pavlogiannis · 2025
Read The Complexity of Testing Message-Passing Concurrency by Zheng Shi, Lasse Møldrup, Umang Mathur, Andreas Pavlogiannis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05162.txt.
Introduction
Zheng Shi and co-authors map the complexity of testing message passing concurrency in a 2025 computer science paper. Programs that talk through channels, as in Go, Rust, and Kotlin, need tests for whether a partial run can be completed consistently. That question is well studied for shared memory, but poorly understood for channels.
The team vary thread count, channel count, and channel capacity to chart where the problem is easy or hard. Some settings admit efficient algorithms that could drive verification tools. Other minimal settings already make the problem hard. The landscape helps tool builders know where automated checks can work.
Catalog record
| CREATOR | Zheng Shi, Lasse Møldrup, Umang Mathur, Andreas Pavlogiannis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 266 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-05162