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

CREATORZheng Shi, Lasse Møldrup, Umang Mathur, Andreas Pavlogiannis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE266 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05162

Browse the full library · About the Tower of Babel