Filter: An Algorithm for Reducing Cascaded Rollbacks in Optimistic Distributed Simulations

We describe a new algorithm, called Filter, that limits the propagation of erroneous computations in optimistic discrete-event distributed simulations. In the proposed algorithm, each message carries a bounded amount of dependency information that describes the assumptions made in the generation of the message, and, in addition, processes keep track of straggler events that have occurred in the system. This knowledge is used by processes to "filter" out messages that depend on a preempted state by discarding them upon receipt. We describe the algorithm and its use in conjunction with time-warp, suggest several ways of reducing its potential overhead by adjusting the extent of filtering, and point out several interesting performance tradeoffs that we are currently exploring. 1 Introduction Distributed discrete-event simulation is potentially a powerful technique for getting speedups in discreteevent simulations. Discrete-event simulations of large systems in many domains, including com..