Efficient Dynamic Concurrency Analysis with Collective Sparse Segment Trees
Open Access
- 30 October 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computer Systems
- Vol. 44 (3) , 1-31
Abstract
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.Keywords
Funding Information
- VILLUM FONDEN, and by a research grant from STIBOFONDEN (VIL42117)
This publication has 42 references indexed in Scilit:
- CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis2024
- Stateless Model Checking Under a Reads-Value-From Equivalence2021
- Boosting Sequential Consistency Checking Using Saturation2020
- Root Causing Linearizability Violations2020
- Gradual Consistency Checking2019
- On (Dynamic) Range Minimum Queries in External Memory2013
- x86-TSOCommunications of the ACM, 2010
- Fast and Generalized Polynomial Time Memory Consistency Verification2006
- Testing Shared MemoriesSIAM Journal on Computing, 1997
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978