Reversible debugging (also known as record and replay) requires making the program behave exactly the same way every time. That way you can "execute backward": at statement n of the program, restart it from the beginning, and stop at statement n-1 (in practice you would take snapshots of the program state along the way so you don't have to re-execute all the way from the beginning of the program).

In the example given here, you could get away with it since control flow doesn't depend on the value of id(object()). But for example, if you had:

    if (id(object()) >> 12) & 1:
        print "foo"
    else:
        print "bar"

You would need to guarantee that id(object()) always returned the same value so that the execution follows the same path.

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.