SERG talk: Probabilistic Concurrency Testing

Abstract

The Probabilistic Concurrency Testing (PCT) algorithm provides nontrivial theoretical guarantees on the probability of detecting concurrency bugs. In this talk, I will provide an overview of the PCT algorithm, which is designed for sequentially consistent multithreaded programs [1], our extension of PCT to testing distributed systems [2], and, more recently, to weak memory concurrency [3], which allows a wider set of concurrency behaviors than sequential consistency.

[1] S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte. “A randomized scheduler with probabilistic guarantees of finding bugs.”, ASPLOS 2010.
[2] B. Kulahcioglu Ozkan, R. Majumdar, F. Niksic, M. Tabaei Befrouei, and G. Weissenbacher. “Randomized testing of distributed systems with probabilistic guarantees.” OOPSLA 2018.
[3] M. Gao, S. Chakraborty, B. Kulahcioglu Ozkan. “Probabilistic concurrency testing for weak memory programs”. ASPLOS 2023. (to appear)