一句话：提出首个亚线性时间随机动态数据竞争检测器，仅处理常数个事件即可高概率发现远距离竞争且无误报。
基于 happens-before 的动态分析能无假阳性地检测数据竞争，但需在每个事件上更新向量时钟，开销高昂，难以用于大规模项目。本文提出一种基于采样的随机竞争检测器：在最坏情况下也只处理输入轨迹中的常数个事件，是首个亚线性时间（o(n)）的动态竞争检测算法，而此前的采样方法仍需线性时间 O(n)。该算法是 ε-race 检测的性质测试器：它从不报告假阳性，并对与任何无竞争轨迹的汉明距离足够远的轨迹，以高概率检测到 ε-race。实验将该算法与最先进的确定性及采样竞争检测器比较，结果显示其运行时间显著降低，且能较频繁地发现竞争。
Happens before-based dynamic analysis is the go-to technique for detecting data races in large scale software projects due to the absence of false positive reports. However, such analyses are expensive since they employ expensive vector clock updates at each event, rendering them usable only for in-house testing. In this paper, we present a sampling-based, randomized race detector that processes only constantly many events of the input trace even in the worst case. This is the first sub-linear time (i.e., running in o ( n ) time where n is the length of the trace) dynamic race detection algorithm; previous sampling based approaches like run in linear time (i.e., O ( n )). Our algorithm is a property tester for -race detection — it is sound in that it never reports any false positive, and on traces that are far, with respect to hamming distance, from any race-free trace, the algorithm detects an -race with high probability. Our experimental evaluation of the algorithm and its comparison with state-of-the-art deterministic and sampling based race detectors shows that the algorithm does indeed have significantly low running time, and detects races quite often.
@article{paperbot2077,
title = {Dynamic Race Detection with O(1) Samples},
author = {Mosaad Al Thokair and Minjian Zhang and Umang Mathur and Mahesh Viswanathan},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {POPL},
year = {2023},
doi = {10.1145/3571238}
}