EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fast Atomicity Monitoring

Hünkar Can Tunç, Yifan Dong, Andreas Pavlogiannis

Proceedings of the ACM on Programming Languages · 08.06.2026 · 10 (PLDI) · 29-52

DOI: 10.1145/3808248 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 08.06.2026. Verfasst von Hünkar Can Tunç und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Villum Fonden, STIBOFONDEN.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 ( n k 3 ) and O ( n k ( 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 ( n k 2 ) . AtomSanitizer operates in an efficient streaming style, is theoretically faster than all existing algorithms, and also has a smaller memory footprint. Moreover, it is the first algorithm designed to use little 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 only a marginal time and space overhead over 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.

Förderung

  • Villum Fonden
  • STIBOFONDEN

Zitieren

APA

Tunç, H. C., Dong, Y., & Pavlogiannis, A. (2026). Fast Atomicity Monitoring. Proceedings of the ACM on Programming Languages, 10(PLDI), 29-52. https://doi.org/10.1145/3808248

Vancouver

Tunç HC, Dong Y, Pavlogiannis A. Fast Atomicity Monitoring. Proceedings of the ACM on Programming Languages. 2026;10(PLDI):29-52. doi:10.1145/3808248

BibTeX
@article{Tun2026,
  author = {Tunç, Hünkar Can and Dong, Yifan and Pavlogiannis, Andreas},
  title = {Fast Atomicity Monitoring},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2026},
  volume = {10},
  number = {PLDI},
  pages = {29--52},
  doi = {10.1145/3808248}
}
Kostenlos starten →