Spatio-temporal correlations and rollback distributions in optimistic simulations

ABSTRACT

In this paper we study the influence of spatio-temporal correlations on the dynamic runtime behavior of the optimistic parallel Time Warp simulation method. By using the Ising spin model, we show experimentally that the distribution of the number of rolled back events behaves as a power-law distribution over a large range of sub-critical Ising temperatures and decays exponentially for super-critical Ising temperatures. For critical Ising temperatures, where long-range correlations occur, the computational complexity of Time Warp and physical complexity of the Ising spin model are entangled and contribute both to the runtime behavior in a nonlinear way.

REFERENCES

• 1: P. Bak, C. Tang, and K. Wiesenfeld. Self-organized criticality. Physical Review A, 38(1):364--374, July 1988.
• 2: Gregory G. Brunk, Understanding self-organized criticality as a statistical process, Complexity, v.5 n.3, p.26-33, Jan.-Feb. 2000 [doi>10.1002/(SICI)1099-0526(200001/02)5:3<26::AID-CPLX6>3.0.CO;2-C]
• 3: V. Frette, K. Christensen, A. Malthe-SCrensen, J. Feder, T. Jossang, and E Meakin. Avalance dynamics in a pile of rice. Nature, 379(6560):49-52, Jan. 1996.
• 4: B. Huberman and N. Glance. Evolutionary games and computer simulations. Proceedings of the National Academy of Sciences of the United States of America, 90(16):7716- 7718, Aug. 1993.
• 5: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 6: Boris D. Lubachevsky, Efficient parallel simulations of dynamic Ising spin systems, Journal of Computational Physics, v.75 n.1, p.103-122, March 1988 [doi>10.1016/0021-9991(88)90101-5]
• 7: B. Overeinder. Distributed Event-driven Simulation: Scheduling Strategies and Resource Management. PhD thesis. Department of Computer Science, University of Amsterdam, Amsterdam, The Netherlands, Nov. 2000.
• 8: B. Overeinder, A. Schoneveld, and P. Sloot. Self-organized criticality in optimistic simulation. Parallel and Distributed Computing Practices, 2001. (Research note accepted for publication).
• 9: B. Overeinder and P. Sloot. Application of Time Warp to parallel simulations with asynchronous cellular automata. In Proceedings of the 1993 European Simulation Symposium, pages 397-402, Delft, The Netherlands, Oct. 1993.
• 10: P. Sloot and B. Overeinder. Time-Warped automata: Parallel discrete event simulation of asynchronous CA's. In Proceedings of the Third International Conference on Parallel Processing and Applied Mathematics, pages 43-62, Kazimierz Dolny, Poland, Sept. 1999.
• 11: L. Sokol, B. Stucky, and V. Hwang. MTW: A control mechanism for parallel discrete simulation. In Proceedings of the 1989 International Conference on Parallel Processing, volume III, pages 250-254, Minneapolis, MN, Aug. 1989.
• 12: H. Stanley. Scaling, universality, and renormalization: Three pillars of modem critical phenomena. Reviews of Modern Physics, 71(2):$358-$366, Mar. 1999.
• 13: H. Stanley, L. Amaral, P. Gopikrishnan, P. lvanov, T. Keitt, and V. Plerou. Scale invariance and universitality: Organizing principles in complex systems. Physica A, 281(1-4):60- 68, June 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Experimentation, Measurement, Performance, Theory