The virtual time paradigm is a method of organizing and synchronizing distributed systems. An implementation of this paradigm, called the Time Warp mechanism, is one of the most important parallel simulation protocols. The Time Warp synchronization mechanism takes an optimistic approach, in which a process executes every message as soon as it arrives. If a message with an earlier timestamp subsequently arrives, the process rolls back its state to the time of the earlier message and re-executes from that point. Thus, the state of each process must be saved regularly (regardless of whether or not rollbacks actually occur).
The amount of storage used for state-saving grows as the simulation progresses. Jefferson observed that at any real time there exits a global virtual time, GVT, such that all executed messages with timestamps earlier than GVT will not be rolled back. Thus, the storage used for saving information with timestamps earlier than GVT can be reclaimed. In addition to garvage collection, GVT can be useful in other areas of Time Warp simulation such as termination detection, snapshots and crash recovery, input and output handling, etc.
The task of finding GVT is not trivial in a distributed environment . The approach used in most distributed Time Warp implementations is based on Samadi's algorithm. This algorithm requires acknowledgement messages, which introduce heavy network traffic. This paper proposes a new algorithm that does not require acknowledgement messages, eliminating 50% of the network traffic in Time Warp simulation.