Rollback sometimes works...if filtered

ABSTRACT

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.

REFERENCES

• 1: Asmussen, S. and Hering, H., Branching Processes, Birkhauser, 1983.
• 2: Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist., 23 (1952), 494--507.
• 3: Gafni, A., Berry, O., Jefferson, D. Optimized virtual synchronization, Proc. 2nd Int. Workshop on Applied Math. and Performance/Reliability Models, Univ. of Rome II (1987), 229--244.
• 4: Jefferson, D. R., Virtual time. ACM Transactions on Programming Languages and Systems, 7, 3 (1985), 404--425.
• 5: Lubachevsky, B. D. Bounded lag distributed discrete event simulation (Extended Abstract), in Distributed Simulation, B. Unger, and D. Jefferson (eds.), SCS, Simulation Series, 19, 3 (1988), 183--192.
• 6: Lubachevsky, B. D. Efficient distributed event driven simulations of multiple-loop networks, Communications of the ACM, 32, 1 (1989), pp. 111--131.
• 7: Lubachevsky, B. D. Scalability of the bounded lag distributed discrete event simulation, in Distributed Simulation, B. Unger, and R. Fujimoto (eds.), SCS, Simulation Series, 21, 2 (1989), 100--107.
• 8: Sokol, L. M., Briscoe, D. P, and Wieland, A. P. MTW: a strategy for scheduling discrete simulation events for concurrent execution, in Distributed Simulation, B. Unger, and D. Jefferson (eds.), Simulation Series, SCS, 19, 3 (1988) 34--42.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance