%0 Conference Paper %1 Zhou:2012:SSD %A Zhou, Jinguo %A Xiao, Xiao %A Zhang, Charles %B Proceedings of the 34th International Conference on Software Engineering %C Piscataway, NJ, USA %D 2012 %I IEEE Press %K Concurrency Debugging Determinism Deterministic %P 892--902 %T Stride: Search-based Deterministic Replay in Polynomial Time via Bounded Linkage %X Abstract—Deterministic replay remains as one of the most effective ways to comprehend concurrent bugs. Existing approaches either maintain the exact shared read-write linkages with a large runtime overhead or use exponential off-line algorithms to search for a feasible interleaved execution. In this paper, we propose Stride, a hybrid solution that records the bounded shared memory access linkages at runtime and infers an equivalent interleaving in polynomial time, under the sequential consistency assumption. The recording scheme eliminates the need for synchronizing the shared read operations, which results in a significant overhead reduction. Comparing to the previous state-of-the-art approach of deterministic replay, Stride reduces, on average, 2.5 times of runtime overhead and produces, on average, 3.88 times smaller logs. %@ 978-1-4673-1067-3

@inproceedings{Zhou:2012:SSD, abstract = {Abstract—Deterministic replay remains as one of the most effective ways to comprehend concurrent bugs. Existing approaches either maintain the exact shared read-write linkages with a large runtime overhead or use exponential off-line algorithms to search for a feasible interleaved execution. In this paper, we propose Stride, a hybrid solution that records the bounded shared memory access linkages at runtime and infers an equivalent interleaving in polynomial time, under the sequential consistency assumption. The recording scheme eliminates the need for synchronizing the shared read operations, which results in a significant overhead reduction. Comparing to the previous state-of-the-art approach of deterministic replay, Stride reduces, on average, 2.5 times of runtime overhead and produces, on average, 3.88 times smaller logs.}, acmid = {2337328}, added-at = {2015-02-24T16:57:56.000+0100}, address = {Piscataway, NJ, USA}, author = {Zhou, Jinguo and Xiao, Xiao and Zhang, Charles}, biburl = {https://www.bibsonomy.org/bibtex/2842ad6046c82d59829482080d4fd312b/gron}, booktitle = {Proceedings of the 34th International Conference on Software Engineering}, description = {Stride: search-based deterministic replay in polynomial time via bounded linkage}, interhash = {5793957a97e252742d238565de83e49c}, intrahash = {842ad6046c82d59829482080d4fd312b}, isbn = {978-1-4673-1067-3}, keywords = {Concurrency Debugging Determinism Deterministic}, location = {Zurich, Switzerland}, numpages = {11}, pages = {892--902}, publisher = {IEEE Press}, series = {ICSE '12}, timestamp = {2015-02-24T16:57:56.000+0100}, title = {Stride: Search-based Deterministic Replay in Polynomial Time via Bounded Linkage}, year = 2012 }