Efficient Dynamic Algorithms to Predict Short Races
Minjian Zhang, Mahesh Viswanathan · 2026
Read Efficient Dynamic Algorithms to Predict Short Races by Minjian Zhang, Mahesh Viswanathan (2026) 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-2603-03141.txt.
Introduction
Minjian Zhang and Mahesh Viswanathan predict data races in concurrent programs before they fully unfold. A race happens when two threads access shared data without proper ordering, and short races, where the two accesses sit close together in an execution trace, are the most plausible to recur. Their 2026 paper builds a monitoring framework for spotting them inside a chosen window size.
Algorithms for two race definitions follow. The happens-before version matches a leading tool's speed while using memory tied to the window, not the whole trace. The sync-preserving version runs faster and leaner than its rival. Experiments confirm the trade: less memory, quicker runs, and significantly more races found under the same budget.
Catalog record
| CREATOR | Minjian Zhang, Mahesh Viswanathan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97553 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03141
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Dynamic Algorithms to Predict Short Races Minjian Zhang, Mahesh Viswanathan Abstract We introduce and study the problem of detecting short races in an observed trace. Specifically, for a race type 𝖱 \mathsf{R} , given a trace σ \sigma and window size 𝗐 \mathsf{w} , the task is to determine whether there exists 𝖱 \mathsf{R} -race ( e 1 , e 2 ) (e_{1},e_{2}) in σ \sigma such that the subtrace starting with e 1 e_{1} and ending with e 2 e_{2} contains at most 𝗐 \mathsf{w} events. We present a monitoring framework for short-race prediction and instantiate the framework for happens-before and sync-preserving races, yielding efficient detection algorithms. Our happens-before algorithm runs in the same time as FastTrack but uses space that scales with log 𝗐 \log\mathsf{w} as opposed to log | σ | \log|\sigma| . For sync-preserving races, our algorithm runs faster and consumes significantly less space than SyncP . Our experiments validate the effectiveness of these short race detection algorithms: they run more efficiently, use less memory, and detect significantly more races under the same budget, offering a reasonable balance between resource usage and predictive power. University of Illinois Urbana-Champaign, [email protected] University of Illinois Urbana-Champaign, [email protected] ccs Software and its engineering Dynamic analysis keywords concurrency, prediction, data race, happens-before † † event-logo: lipics-logo-bw † † runningauthor: M. Zhang and M. Viswanathan † † copyright: Anonymous Author(s) Developing reliable concurrent programs is a complex task, making formal reasoning principles essential for their analysis. The difficulty in designing and verifying concurrent systems stems from the inherent nondeterminism in program behavior caused by inter-process communication and scheduling. Managing this nondeterminism during development is challenging, often resulting in error-prone software. Furthermore, concurrency-related bugs are notoriously difficult to reproduce manually, highlighting the need for automated detection techniques to improve software development productivity. A data race (or simply a race) occurs when a thread in a multi-threaded program accesses a shared memory location while another thread modifies it without proper synchronization. Data races often signal serious program defects [ 27 ] and have been associated with data corruption, compilation failures [ 33 , 8 , 21 ] , and critical system failures [ 48 , 9 ] . As a result, extensive research has focused on detecting and preventing data races in multi-threaded programs. Although static techniques for data race detection exist, dynamic race detection methods are more widely used due to their superior scalability and precision. The goal of dynamic race detection is to analyze an observed program trace to determine whether it contains evidence of a data race in the program that generated it. A key objective of this approach is to be predictive — not only identifying data races in the observed trace but also uncovering races in potential alternate executions that the program could exhibit. This predictive capability improves the practical utility of dynamic race detection. However, the requirement to be predictive also makes the problem computationally challenging — dynamic race detection is NP -complete and \text{W}[1] -hard, rendering it fixed-parameter intractable [ 30 , 23 ] . The challenge of intractability has driven research into specialized types of predictive data races [ 24 , 41 , 44 , 22 , 5 , 29 , 36 , 34 , 37 , 31 , 43 ] . These approaches aim to balance predictive power with computational tractability. Race definitions typically rely on either partial orders [ 24 , 44 , 22 , 29 ] or constraints on the types of alternate executions considered [ 41 , 34 , 31 , 43 ] . Even if a race type is tractable, meaning it has a polynomial-time algorithm, the practical overhead can still be prohibitively high, limiting the size of traces that can be analyzed. Even for race detection algorithms that run in a single pass with linear-time streaming, lower bounds indicate that they require memory proportional to the trace size [ 22 , 31 ] , which can be substantial. To address this, windowing [ 44 , 41 ] has been proposed as a technique to reduce overhead in dynamic race detection. This approach divides the trace into subtraces of a fixed length (say) \mathsf{w} , and the algorithm searches for races only within each subtrace. By limiting analysis to bounded-length segments, windowing helps control computational overhead, making it feasible to analyze larger traces. Windowing imposes a key limitation on predictive analysis. Certifying a predictive race typically depends on context outside the two conflicting events and the events in between. If some key events in the context are outside the window, no algorithm can soundly certify the race, even though the two racy events themselves are in view. Therefore we focus on a problem that generalizes windowing. Rather than limiting race detection to predefined subtraces, we investigate whether a trace contains short races — races where the distance between the events involved is bounded. Our approach augments the window with a constant-space summary that captures exactly the out-of-window context required to certify predictive races. Beyond reducing computational overhead, a key motivation for windowing and our method of detecting short races is that, in practice, racy programs frequently manifest short races. Furthermore, efficient algorithms for detecting such short races can also enhance randomized approaches to race detection [ 45 ] . We present a monitoring framework for short-race detection on streaming traces: as the trace is processed online, the monitor maintains a fixed-size window as well as compact summary of the relevant history and updates it incrementally under window advances. We then instantiate the framework for two widely used race notions—happens-before and sync-preserving races. Happens-before races [ 24 ] are the oldest and most widely used data race definition. It is defined using the happens-before partial order and underpins industrial tools like ThreadSanitizer [ 42 ] . Sync-preserving races [ 31 ] is a generalization of happens-before with greater predictive power. Both race types can be detected using linear-time, single-pass algorithms, though any linear-time algorithm for detecting sync-preserving races must use linear space [ 31 ] . We explore whether these race definitions allow for more efficient detection of short races with reduced overhead. Our results are summarized in Table 1 . \mathsf{R} -race Race Detection Short Races Happens-before Time: O(\mathsf{N}\mathsf{T}) Time: O(\mathsf{N}\mathsf{T}) Space: O((\mathsf{T}+\mathsf{V}+\mathsf{L})\mathsf{T}\log\mathsf{N}) Space: O(\mathsf{w}+(\min(\mathsf{w},\mathsf{V}+\mathsf{L})+\mathsf{T})\mathsf{T}\log\mathsf{w}) Sync-Preserving Time: O(\mathsf{N}\mathsf{T}^{2}+\mathsf{A}\mathsf{V}\mathsf{T}^{3}) Time: O(\mathsf{N}\mathsf{T}(\min(\mathsf{w},\mathsf{T}))+\mathsf{A}\mathsf{T}(\min(\mathsf{w},\mathsf{V}\mathsf{T}^{2}))) Space: O(\mathsf{V}\mathsf{L}\mathsf{T}^{3}+\mathsf{N}\mathsf{T}\log\mathsf{N}) Space: O(\min(\mathsf{w},\mathsf{V}\mathsf{T})\mathsf{L}\mathsf{T}^{2}+(\mathsf{w}+\mathsf{V}+\mathsf{L})\mathsf{T}\log\mathsf{N}) Table 1 : Overview of results based on the following parameters. \mathsf{N} is the size of the trace, \mathsf{w} is the length of the short race, \mathsf{T} is the number of threads, \mathsf{V} is the number of variables, \mathsf{L} is the number of locks, and \mathsf{A} is the number of acquire events in the trace. Our algorithm for detecting short happens-before races of size \mathsf{w} maintains a sliding window of the most recent \mathsf{w} events and checks for races within this window. The correctness of this strategy hinges on the observation that whether a pair (e_{1},e_{2}) is ordered by happens-before depends only on the events between them. Our approach builds on FastTrack [ 18 ] , the most efficient known HB detector, but modifies it to avoid the limitations of naïve windowing. Simply restricting the search to the last \mathsf{w} events—while keeping standard vector-clock