rollback sometimes works...if filtered
We introduce a new parallel discrete event simulation algorithm called filtered rollback. It is a combination of the Time Warp and bounded lag simulation algorithms introduced previously. The "filter" postpones event processing in some subsystems in favor of safer simulation. The filter may be tuned by the simulationist; at one extreme the algorithm is conservative, i.e., free from rollback, and at the other extreme the algorithm is purely optimistic, i.e., relying exclusively on rollback. We prove that rollback cascading, wherein a "chain reaction" of secondary and higher generation rollbacks appear in the simulation, can be bounded by an appropriate tuning. The tuning achieves a trade-off between the two extremes which yields an efficient and scalable algorithm. Our method of proof uses a representation of the rollback cascading as a tree and models such a tree as a Galton-Watson branching process on which an additional structure is defined, a random walk with a barrier.
filtering parallel discrete event simulation simulation algorithm combinational timing warp event processes process tuning generation efficiency scalability method representation tree model structure random walks barrier