Ah, you've caught me out on my sloppy use of English.

What I should have said is that the address space layout is a source of non-determinism that would otherwise need to be accounted for in the recording of a program.

Further, I hold to the view that given a program, knowledge of the thread execution schedule/scheduler and the results of external calls, a program's execution should be deterministic.

Thinking about this now, I realize disabling ASLR shouldn't be enough to fix this problem since recording and replaying are sufficiently different.