The time warp mechanism is one of the useful paradigms to carry out adistributed discrete event simulation, where the synchronization of events canbe determined a priori when the program is being executed. The forwardcomputation performed optimistically has to be rolled back when an out-of-ordersynchronization message is received. This excessive amount of rollbackseriously jeopardizes the performance of a time warp mechanism. Semantics ofthe synchronization messages being sent in a time warp execution can beexploited to reduce the amount of rollback. In particular, the commutativityand dependency properties of messages can be used to avoid certain types ofrollback. For example, two commutative messages can be processed in any orderand the resultant computation remains valid. In this paper, the semantics onthe messages are defined and the protocols for handling such kinds of messagesin the time warp mechanism and several optimizations are presented.