Optimality considerations of 'Time Warp' parallel simulation

This paper derives a relationship between a conservative optimal simulation and the 'Time Warp' or 'optimistic' parallel simulation, and compares the performance of the Time Warp simulation with Chandy-Misra conservative simulation. We show that Time Warp simulation with aggressive cancellation is not conservative optimal in general, even under the assumption that the operational overhead virt is 0. We derive a sufficient condition for Time Warp to be conservative optimal and show some simulation problems that meet this condition (referred to as Time Warp simulations that satisfy the sufficient conservative optimal condition, or TWSO.) We show that by applying the lazy cancellation technique to TWSO, Time Warp always outperforms a conservative optimal simulation. Given equivalently favorable assumptions for both the Time Warp approach and the Chandy-Misra approach, we show that the Time Warp approach outperforms the Chandy-Misra approach in every feedforward network simulation. For feedback networks without lookahead, we show that in most cases Time Warp outperforms Chandy-Misra.