Debugging parallel programs is still a challenge although many debugging techniques and corresponding tools have been developed. One reason why parallel programs are difficult to debug is the irreporducibility effect, which is caused by nondeterminism occuring at process interaction. Solutions to this problem are provided by so-called record&replay mechanisms or replay techniques. However, the rather long waiting time during replay often prohibits inclusion of these techniques to debugging tools, which must provide some degree of interactivity for user's investigations. This paper analyzes the possibility of combining debugging with checkpointing to shorten waiting time during re-executions. Related work in this area either cannot ensure a short waiting time or creates other effects on the autonomy of processes. The EROS approach introduces the replay dependence relation, which allows to minimize the waiting time without the restrictions above. In fact, EROS provides a small upper band of the replay time during debugging nondeterministic message passing programs.