SCIENCE@home

Efficient Dynamic Algorithms to Predict Short Races

Minjia Zhang,Mahesh Viswanathan

Published 2026 in Unknown venue

ABSTRACT

We introduce and study the problem of detecting short races in an observed trace. Specifically, for a race type $R$, given a trace $\sigma$ and window size $w$, the task is to determine whether there exists an $R$-race $(e_1, e_2)$ in $\sigma$ such that the subtrace starting with $e_1$ and ending with $e_2$ contains at most $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 w$ as opposed to $\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.

PUBLICATION RECORD

  • Publication year

    2026

  • Venue

    Unknown venue

  • Publication date

    2026-03-03

  • Fields of study

    Computer Science

  • Identifiers
    arXiv 2603.03141
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-46 of 46 references · Page 1 of 1

CITED BY

  • No citing papers are available for this paper.

Showing 0-0 of 0 citing papers · Page 1 of 1