Efficient Dynamic Concurrency Analysis with Collective Sparse Segment Trees

Dynamic analyses are a standard approach to analyzing and testing concurrent programs. Such techniques observe program traces σ and analyze them to infer the presence or absence of bugs. At its core, each analysis maintains a partial order P that represents order dependencies between the events of σ. Naturally, the scalability of the analysis largely depends on maintaining P efficiently. The standard data structure for this task has thus far been Vector Clocks. These, however, are slow for analyses that follow a non-streaming style, costing O(n) time for inserting (and propagating) each new ordering in P, where n is the size of σ, while they cannot handle the deletion of existing orderings. In this paper we develop Collective Sparse Segment Trees (CSSTs), a simple but elegant data structure for maintaining a partial order P. CSSTs thrive when the width k of P is much smaller than the size n of its domain, allowing inserting, deleting, and querying for orderings in P to run in O(log n) time. For a concurrent trace, k normally equals the number of its threads, and is orders of magnitude smaller than its size n, making CSSTs fitting for this setting. Our experiments confirm that CSSTs are the best data structure currently to handle a range of dynamic analyses from existing literature.

• Publication year

  2025

• Venue

  ACM Transactions on Computer Systems

• Publication date

  2025-10-30

• Fields of study

  Not labeled

• Identifiers
  DOI 10.1145/3773085
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimistic Prediction of Synchronization-Reversal Data Races

  2024cited by this paper
• CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis

  2024cited by this paper
• How Hard Is Weak-Memory Testing?

  2023cited by this paper
• Probabilistic Concurrency Testing for Weak Memory Programs

  2023cited by this paper
• Sound Dynamic Deadlock Prediction in Linear Time

  2023cited by this paper
• Optimal Reads-From Consistency Checking for C11-Style Memory Models

  2023cited by this paper
• A tree clock data structure for causal orderings in concurrent executions

  2022cited by this paper
• Stateless Model Checking under a Reads-Value-From Equivalence

  2021cited by this paper
• Detecting concurrency vulnerabilities based on partial orders of memory and thread events

  2021influential reference
• Sound and efficient concurrency bug prediction

  2021influential reference
• C11Tester: a race detector for C/C++ atomics

  2021influential reference
• The Complexity of Dynamic Data Race Prediction

  2020cited by this paper
• The reads-from equivalence for the TSO and PSO memory models

  2020cited by this paper
• Boosting Sequential Consistency Checking Using Saturation

  2020cited by this paper
• Root Causing Linearizability Violations

  2020cited by this paper
• Atomicity Checking in Linear Time using Vector Clocks

  2020cited by this paper
• SmartTrack: efficient predictive race detection

  2019cited by this paper
• Weak-consistency specification via visibility relaxation

  2019cited by this paper
• Gradual Consistency Checking

  2019cited by this paper
• On the complexity of checking transactional consistency

  2019influential reference
• Optimal stateless model checking for reads-from equivalence under sequential consistency

  2019cited by this paper
• Efficient scalable thread-safety-violation detection: finding thousands of concurrency bugs during testing

  2019cited by this paper
• Fast, sound, and effectively complete dynamic race prediction

  2019influential reference
• UFO: Predictive Concurrency Use-After-Free Detection

  2018influential reference
• High-coverage, unbounded sound predictive race detection

  2018cited by this paper
• Sound deadlock prediction

  2018cited by this paper
• BARRACUDA: binary-level analysis of runtime RAces in CUDA programs

  2017cited by this paper
• Data-centric dynamic partial order reduction

  2016cited by this paper
• DoubleChecker: efficient sound and precise atomicity checking

  2014cited by this paper
• On (Dynamic) Range Minimum Queries in External Memory

  2013cited by this paper
• CDSchecker: checking concurrent data structures written with C/C++ atomics

  2013cited by this paper
• x86-TSO

  2010cited by this paper
• ThreadSanitizer: data race detection in practice

  2009cited by this paper
• FastTrack: efficient and precise dynamic race detection

  2009cited by this paper
• Finding and Reproducing Heisenbugs in Concurrent Programs

  2008cited by this paper
• Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs

  2008cited by this paper
• Fast and Generalized Polynomial Time Memory Consistency Verification

  2006influential reference
• Virtual Time and Global States of Distributed Systems

  2002cited by this paper
• Accordion Clocks: Logical Clocks for Data Race Detection

  2001cited by this paper
• Testing Shared Memories

  1997cited by this paper
• Time, clocks, and the ordering of events in a distributed system

  1978cited by this paper

• No citing papers are available for this paper.