一句话：提出 AtomSanitizer，以 O(nk²) 时间流式检测冲突可串行化，并首次支持低锁并发运行时监控。
原子性是并发程序的基本抽象，原子性违反是常见并发缺陷，动态判定执行是否满足冲突可串行化规约仍面临效率挑战。现有 RegionTrack 和 Aerodrome 的复杂度分别为 O(nk³) 与 O(nk(k+v+ℓ))。本文提出 AtomSanitizer，在 n 个事件、k 个线程、v 个位置、ℓ 个锁的迹上以 O(nk²) 时间流式检测冲突可串行化，理论快于已有算法且内存更省，并首次为并发监控设计最小锁机制。标准基准显示其始终更快；集成到 TSAN 后，相比数据竞争检测引擎仅增加极小时间与空间开销，首次证明该算法适合运行时监控。
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.