Shared-memory parallel programs are inherently nondeterministic, making it difficult to diagnose rare bugs and to achieve deterministic execution. Existing multithreaded record & replay approaches have serious limitations such as relying on custom hardware, handling only data-race-free executions, or slowing programs by an order of magnitude. Furthermore, language virtual machines (VMs) such as Java VMs (JVMs) introduce various sources of nondeterminism that thwart demonstrating deterministic replay.

This paper introduces an approach for multithreaded record & replay based on tracking and reproducing shared-memory dependences accurately and efficiently. Building on prior work that introduces an efficient dependence recorder, we develop a new analysis for replaying dependences. To demonstrate multithreaded record & replay, we modify a JVM to support a new methodology that enables demonstrating and evaluating replay in the inherently nondeterministic JVM. Overall, the performance of both recorded and replayed executions compares favorably with performance reported by prior work for competing record & replay approaches.