Yifan Dong
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Yifan Dong has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Andreas Pavlogiannis
Aarhus University, Aarhus, Denmark
2 shared publications - Hünkar Can Tunç
Aarhus University, Denmark
2 shared publications - Ameya Prashant Deshmukh
IIT Bombay
1 shared publication - Berk Cirisci
Amazon Web Services, Berlin, Germany
1 shared publication - Constantin Enea
LIX, CNRS, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France
1 shared publication
Latest Publications
- Open Access
- 8 June 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (PLDI) , 29-52
Fast Atomicity Monitoring
Atomicity is a fundamental abstraction in concurrency, specifying that program behavior can be understood by considering specific code blocks executing atomically. However, atomicity invariants are tricky to maintain while also optimizing for code efficiency, and atomicity violations are a common root cause of many concurrency bugs. To address this problem, several dynamic techniques have been developed for testing whether a program execution adheres to an atomicity specification, most often instantiated as conflict serializability . The efficiency of the analysis has been targeted in various papers, with the state-of-the-art algorithms RegionTrack and Aerodrome achieving a time complexity O ( nk 3 ) and O ( nk ( k + v + ℓ)), respectively, for a trace σ of n events, k threads, v locations, and ℓ locks. In this paper we introduce AtomSanitizer, a new algorithm for testing conflict serializability, with time complexity O ( nk 2 ). AtomSanitizer operates in an efficient streaming style, is theoretically faster than all existing algorithms, and also has a smaller memory footprint. Moreover, AtomSanitizer is the first algorithm designed to incur minimal locking when deployed in a concurrent monitoring setting. Experiments on standard benchmarks indicate that AtomSanitizer is always faster in practice than all existing conflict-serializability testers. Finally, we also implement AtomSanitizer inside the TSAN framework, for monitoring atomicity in real time. Our experiments reveal that AtomSanitizer incurs minimal time and space overhead compared to the data-race detection engine of TSAN, and thus is the first algorithm for conflict serializability demonstrated to be suitable for a runtime monitoring setting.
- 8 June 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (PLDI) , 29-52
Open AccessFast Atomicity Monitoring
Atomicity is a fundamental abstraction in concurrency, specifying that program behavior can be understood by considering specific code blocks executing atomically. However, atomicity invariants are tricky to maintain while also optimizing for code efficiency, and atomicity violations are a common root cause of many concurrency bugs. To address this problem, several dynamic techniques have been developed for testing whether a program execution adheres to an atomicity specification, most often instantiated as conflict serializability . The efficiency of the analysis has been targeted in various papers, with the state-of-the-art algorithms RegionTrack and Aerodrome achieving a time complexity O ( nk 3 ) and O ( nk ( k + v + ℓ)), respectively, for a trace σ of n events, k threads, v locations, and ℓ locks. In this paper we introduce AtomSanitizer, a new algorithm for testing conflict serializability, with time complexity O ( nk 2 ). AtomSanitizer operates in an efficient streaming style, is theoretically faster than all existing algorithms, and also has a smaller memory footprint. Moreover, AtomSanitizer is the first algorithm designed to incur minimal locking when deployed in a concurrent monitoring setting. Experiments on standard benchmarks indicate that AtomSanitizer is always faster in practice than all existing conflict-serializability testers. Finally, we also implement AtomSanitizer inside the TSAN framework, for monitoring atomicity in real time. Our experiments reveal that AtomSanitizer incurs minimal time and space overhead compared to the data-race detection engine of TSAN, and thus is the first algorithm for conflict serializability demonstrated to be suitable for a runtime monitoring setting.
- Open Access
- 30 October 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computer Systems
- Vol. 44 (3) , 1-31
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.
- 30 October 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computer Systems
- Vol. 44 (3) , 1-31
Open AccessEfficient 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.