In a method of identifying a globally consistent state in a multithreaded program, a plurality of locally consistent states is identified, in which a locally consistent state of a thread comprises a set of memory locations and their corresponding data values accessed between points in the multithreaded program where no locks are held. Globally consistent states are identified based at least in part on the locally consistent states.