5 papers
Fixed Parameter Tractable Linearizability Monitoring
Lee Zheng Han, Umang Mathur
We study the linearizability monitoring problem, which asks whether a given concurrent history of a data structure is equivalent to some sequential execution of the same data struc…
Compiling Away the Overhead of Race Detection
Alexey Paznikov, Andrey Kogutenko, Yaroslav Osipov +2
Dynamic data race detectors are indispensable for flagging concurrency errors in software, but their high runtime overhead limits their adoption. This overhead stems primarily from…
The Complexity of Testing Message-Passing Concurrency
Zheng Shi, Lasse Møldrup, Umang Mathur +1
A key computational question underpinning the automated testing and verification of concurrent programs is the consistency question - given a partial execution history, can it be c…
Efficient Decrease-and-Conquer Linearizability Monitoring
Lee Zheng Han, Umang Mathur
Linearizability has become the de facto correctness specification for implementations of concurrent data structures. While formally verifying such implementations remains challengi…
Enhanced Data Race Prediction Through Modular Reasoning
Zhendong Ang, Azadeh Farzan, Umang Mathur
There are two orthogonal methodologies for efficient prediction of data races from concurrent program runs: commutativity and prefix reasoning. There are several instances of each…