Executing result of parallel programs which communicate by passing messages, can be nondeterministic due to variations in process scheduling and message latencies. Such nondeterminacy can cause serious problems while debugging: subsequent executions of the program may not reproduce the original bug. Therefore, a tracing and replaying mechanism is introduced into parallel debugging environments. This paper discussed an advanced algorithm for tracing and replaying, and its implementation.