CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis
Hünkar Can Tunç, Ameya Prashant Deshmukh, Berk Çirişci, Constantin Enea, Andreas Pavlogiannis · 2024
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.