Program execution can be monitored and recorded for later playback. Certain state changes that can be predicted via a virtual processor during playback need not be recorded, so a compressed recording can be stored. To facilitate random access with respect to time during playback, key frames can be stored within the compressed recording. An index mechanism can associate key frames with particular memory addresses. Additionally, a snapshot of values for memory addresses can be used to further facilitate determining the value of a memory address without having to simulate execution. Multiprocessor executions can be supported, and playback can be done on a machine type different from that on which recording took place.