Virtual Time III, Part 3: Throttling and Message Cancellation

This is Part 3 of a trio of papers that unify in a natural way the two historically distinct parallel discrete event synchronization paradigms, optimistic and conservative, combining the best properties of both into a single framework called Unified Virtual Time (U V T) . In this part, we survey the synchronization effects that can be achieved by restricting to corner cases the relationships permitted among the control variables, GVT , CVT , TVT , and [VT , which were defined in Part 1 . We also survey various throttling policies from the literature and describe how they can be implemented in U V T by controlling the value of TVT , including policies that can take advantage of rollback in addition to LP blocking. A significant result is a new category of efficient and higher precision throttling algorithms for optimistic execution that are based on optimistic lookahead , defined in a way that is symmetric to what we now call the conservative lookahead information that is traditionally used for conservative synchronization. Finally, we present a novel algorithm allowing the choice between lazy and aggressive cancellation to be made on a message-by-message basis using either external logic expressed in the model code, or policy code internal to the simulator, or a mixture of both. CCS Concepts: center dot Computing methodologies - Modeling and simulation ; Simulation types and techniques ; Discrete-event simulation ; Distributed simulation ; Massively parallel and highperformance simulations ; Distributed computing methodologies; center dot Theory of computation - Design and analysis of algorithms ; Parallel algorithms ; Massively parallel algorithms ;