Adaptive algorithms vs. Time Warp: an analytical comparison

ABSTRACT

Adaptive synchronization algorithms have been proposed to improve upon conservative and optimistic algorithms. We present the first known analytical comparison of adaptive, optimistic algorithms and Time Warp. We define a class of adaptive protocols, the asynchronous adaptive waiting protocols (AAWPs) and identify several practical protocols that belong to this class. We show that Time Warp can outperform an AAWP arbitrarily. We describe the Elastic Time Algorithm (ETA), a particular AAWP and show that ETA can outperform Time Warp arbitrarily.

REFERENCES

• 1: Ball, D. and S. Hoyt. 1990. The adaptive Time Warp concurrency control algorithm. Proceedings of the SCS Multiconference on Distributed Simulation, 174- 177.
• 2: Chandy, M. and J. Misra. 1979. Distributed Simulation: A case study in the design and verification of distributed programs. IEEE Transactions on Software Engineering, Vol. SE-5, No. 5, 440-452.
• 3: Alois Ferscha , Satish K. Tripathi, Parallel and distributed simulation of discrete event systems, University of Maryland at College Park, College Park, MD, 1994
• 4: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 5: Hamnes, D.O. and A. Tripathi. 1994. Evaluation of a local adaptive protocol for distributed discrete event simulation. Proceedings of the 1994 International Conference on Parallel Processing, Vol. III, 127-134.
• 6: 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]
• 7: Lipton, R.J. and D.W. Mizelt 1990. Time Warp vs. Chandy-Misra: A worst-case comparison. Proceedings of the 1990 SCS Multiconference on Distributed Simulation, 137-143.
• 8: B. Lubachevsky , A. Shwartz , A. Weiss, Rollback sometimes works...if filtered, Proceedings of the 21st conference on Winter simulation, p.630-639, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76819]
• 9: Boris Lubachevsky , Adam Schwartz , Alan Weiss, An analysis of rollback-based simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.2, p.154-193, April 1991 [doi>10.1145/116890.116912]
• 10: Madisetti, V.K., 1993. Randomized algorithms for selfsynchronization. Private communication.
• 11: Jeff McAffer, A unified distributed simulation system, Proceedings of the 22nd conference on Winter simulation, p.415-422, December 09-12, 1990, New Orleans, Louisiana, United States
• 12: Carmen M. Pancerella , Paul F. Reynolds, Jr., Disseminating critical target-specific synchronization information in parallel discrete event simulations, Proceedings of the seventh workshop on Parallel and distributed simulation, p.52-59, May 16-19, 1993, San Diego, California, United States
• 13: P. L. Reiher , F. Wieland , D. Jefferson, Limitation of optimism in the time warp operating system, Proceedings of the 21st conference on Winter simulation, p.765-770, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76834]
• 14: Paul F. Reynolds, Jr., A spectrum of options for parallel simulation, Proceedings of the 20th conference on Winter simulation, p.325-332, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318209]
• 15: Sudhir Srinivasan , Paul F. Reynolds, Jr., Non-interfering GVT computation via asynchronous global reductions, Proceedings of the 25th conference on Winter simulation, p.740-749, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256834]
• 16: Sudhir Srinivasan , Paul F. Reynolds, Jr., NPSI adaptive synchronization algorithms for PDES, Proceedings of the 27th conference on Winter simulation, p.658-665, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224705]
• 17: Paul F. Reynolds, Jr., Adaptive algorithms vs. Time Warp: An analytical comparison, University of Virginia, Charlottesville, VA, 1995
• 18: Jeff S. Steinman, Breathing Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.109-118, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Adaptive and iterative quadrature

General Terms:
Algorithms, Management, Theory