An analysis of rollback-based simulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An analysis of rollback-based simulation

Full text

Pdf (2.47 MB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 1 , Issue 2 (April 1991) table of contents

Pages: 154 - 193

Year of Publication: 1991

ISSN:1049-3301

Authors

Boris Lubachevsky	AT&T Bell Labs, Murray Hill, NJ
Adam Schwartz	Technion, IIT, Haifa, Israel
Alan Weiss	AT&T Bell Labs, Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 44, Citation Count: 25

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/116890.116912 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ALDER, B. J., AND WAINWRIGI-tT, T E. Studies in molecular dynamics I. General method J. Chem. Phys. 31, 2 (1959), 459-466.
	2	ASMUSSEN, S Some Martingale methods in the limit theory of supercritical branching Processes. In Branching Processes, A Joffe and P. Ney, Eds., Marcel Dekker, New York, 1978, 1-26.
	3	ASMUSSEN, S., AND HERING, H. Branching Processes. Bn'khauser, 1983.
	4	AzENeOT% R., AND RUGET, G M~langes d'~quations diff~rentielles et grands ~cartes ~ la loi des grands hombres. Z. Wahr. 38 (1977), 1-54.
	5	BmCINS, J.D. Chernoff's theorem m the branching random walk. J. AppI. Prob. 14 (1977), 630 636.
	6	BmGINS, J. D, LUBACHEVSKY, B D., SHWARTZ, A., AND WEISS, A A branching random walk with a barrier Ann Appl. Prob. 1, 4 (Nov. 1991).
	7	CHE~NOFF, H. A measure of asymptotic efficiency for tests of a hypothesm based on the sum of observations. Ann. Math. Statist. 23 (1952), 494-507.
	8	CHUN(;, M. Y, AND CSUNO, Y An experimental analysis of simulation clock advancement in parallel logic simulation on an SIMD machine. In Proceedings of the SCS Multzconference on Advances ~n Parallel and Distmbuted Simulat~or~. Szmulatzon Ser~es, SCS. 23~ 1(1991), 125-132.
	9	FUJIMOrO, R. M. Performance measurements of dmtributed simulation strategies. In Proceedings of the 1988 SCS Multico,ference S~mulat~on Ser~es, SCS. 19, 3 14-20
	10	Fu.JmoTo, R M. Time warp on a shared memory multlprocessor. In Procee&ngs of 1989 International Conference on Parallel Processing, pp III-242 III-249.
	11	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]
	12	GAFNI, A., BERRY, 0., AND JEFFERSON, D. Optimized wrtual synchronization. In Proceedings of 2nd International Workshop on Applied Mathematzcs and Performance/Relmb~l~(~ Models (Univ. of Rome II), 1987, pp 229 244
	13	Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.1-12, April 1990, Univ. of Colorado, Boulder, Colorado, United States
	14	HONTALES, P., BECKMAN, B. ET AL. Performance of the colliding pucks simulation of the Time Warp operating systems. In Proceedings of 1989 SCS Multiconference. Simulatwn Series, SCS. 21, 2 (1989), 3-7.
	15	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]
	16	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
	17	Stephen S. Lavenberg , Richard R. Muntz , Behrokh Samadi, Performance Analysis of a Rollback Method for Distributed Simulation, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.117-132, May 25-27, 1983
	18	LIN, Y-B., AND LAZOWSKA, E.D. Optimality considerations for "time warp" parallel simulation. In Distributed Simulatwn 1990. SCS Simulation Series. (1990), 29-34.
	19	B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
	20	LUBACEEVSKY, B.D. Scalability of the Bounded Lag distributed discrete event simulation. In Distributed Simulation, B. Unger and R. Fujimoto Eds. Simulatwn Series. SCS. 21, 2 (1989), 100-107
	21	LUBACHEVSKY, B.D. Simulating colliding rigid disks in parallel using bounded lag without Time Warp. In Proceedings of 1990 SCS Multwonference. Simulatwn Series. SCS. 22, 1 (1990), 194-202.
	22	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]
	23	LUBACHEVSKY, B. D., SHWARTZ, A., AND WEISS, A. The stability of a branching random walk with a barrier. EE. PUB 748, Technion, Israel, 1990.
	24	MADISETTI, V., WALRAND, J., AND MESSERSCHMITT, D. Synchronization in message-passing computers, models, algorithms and analysis. Simulation Series. SCS. 22 (1990), 35-48.
	25	Debasis Mitra , Isi Mitrani, Analysis and Optimum Performance of Two Message-Passing Parallel Processors Synchronized by Rollback, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.35-50, December 19-21, 1984
	26	David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
	27	Behrokh Samadi, Distributed simulation, algorithms and performance analysis (load balancing, distributed processing), 1985
	28	SHEPP, L.A. Connectedness of certain random graphs. Israel J. Math. 67, (1989), 23-33.
	29	SOKOL, L. M., BRISCcE, D. P., AND WIELAND, A.P. MTW: a strategy of scheduling discrete simulation events for concurrent execution. In Distributed Simulation, B. Unger and D. Jefferson, Eds. Simulatwn Series SCS. 19, 3 (1988), 34-42.
	30	SOKOL, L. M., AND STUCKY, B.K. MTW: Experimental results for a constrained optimistic scheduling paradigm. In Distributed Simulation, D. Nicol, Ed. Simulation Series 22, 1/2 (1990), 169-173.

CITED BY 25

	Ian F. Akyildiz , Liang Chen , Samir R. Das , Richard M. Fujimoto , Richard F. Serfozo, Performance analysis of “Time Warp” with limited memory, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.213-224, June 1992
	Bernard P. Zeigler , Sankait Vahie, DEVS formalism and methodology: unity of conception/diversity of application, Proceedings of the 25th conference on Winter simulation, p.573-579, December 12-15, 1993, Los Angeles, California, United States
	Sudhir Srinivasan , Paul F. Reynolds, Jr., Elastic time, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.2, p.103-139, April 1998
	Hassan Rajaei , Rassul Ayani , Lars-Erik Thorelli, The local Time Warp approach to parallel simulation, ACM SIGSIM Simulation Digest, v.23 n.1, p.119-126, July 1993
	Hany H. Ammar , Su Deng, Time warp simulation using time scale decomposition, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.2, p.158-177, April 1992
	Samir R. Das, Estimating the cost of throttled execution in time warp, ACM SIGSIM Simulation Digest, v.26 n.1, p.186-189, July 1996
	Paul F. Reynolds, Jr. , Carmen M. Pancerella , Sudhir Srinivasan, Making parallel simulations go fast, Proceedings of the 24th conference on Winter simulation, p.646-656, December 13-16, 1992, Arlington, Virginia, United States
	Richard Fujimoto , David Nicol, State of the art in parallel simulation, Proceedings of the 24th conference on Winter simulation, p.246-254, December 13-16, 1992, Arlington, Virginia, United States
	Samir R. Das , Richard M. Fujimoto, Adaptive memory management and optimism control in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.2, p.239-271, April 1997
	Samir R. Das, Adaptive protocols for parallel discrete event simulation, Proceedings of the 28th conference on Winter simulation, p.186-193, December 08-11, 1996, Coronado, California, United States
	Robert Rönngren , Michael Liljenstam , Rassul Ayani , Johan Montagnat, Transparent incremental state saving in time warp parallel discrete event simulation, ACM SIGSIM Simulation Digest, v.26 n.1, p.70-77, July 1996
	Vikas Jha , Rajive Bagrodia, Simultaneous events and lookahead in simulation protocols, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.10 n.3, p.241-267, July 2000
	Kevin Jones , Samir R. Das, Combining optimism limiting schemes in time warp based parallel simulations, Proceedings of the 30th conference on Winter simulation, p.499-506, December 13-16, 1998, Washington, D.C., United States
	Sudhir Srinivasan , Paul F. Reynolds, Jr., Adaptive algorithms vs. Time Warp: an analytical comparison, Proceedings of the 27th conference on Winter simulation, p.666-673, December 03-06, 1995, Arlington, Virginia, United States
	Christopher D. Carothers , Richard M. Fujimoto , Paul England, Effect of communication overheads on Time Warp performance: an experimental study, ACM SIGSIM Simulation Digest, v.24 n.1, p.118-125, July 1994
	Kaushik Ghosh , Richard M. Fujimoto , Karsten Schwan, Time Warp simulation in time constrained systems, ACM SIGSIM Simulation Digest, v.23 n.1, p.163-166, July 1993
	Seng Chuan Tay , Yong Meng Teo , Rassul Ayani, Performance analysis of time warp simulation with cascading rollbacks, ACM SIGSIM Simulation Digest, v.28 n.1, p.30-37, July 1998
	Samir R. Das , Richard M. Fujimoto, An adaptive memory management protocol for Time Warp parallel simulation, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.201-210, May 1994
	Alex Chung Hen Chow , Bernard P. Zeigler, Parallel DEVS: a parallel, hierarchical, modular, modeling formalism, Proceedings of the 26th conference on Winter simulation, p.716-722, December 11-14, 1994, Orlando, Florida, United States
	Jinsheng Xu , Moon Jung Chung, Predicting the Performance of Synchronous Discrete Event Simulation, IEEE Transactions on Parallel and Distributed Systems, v.15 n.12, p.1130-1137, December 2004
	Jinsheng Xu , Moon Jung Chung, Predicting the performance of synchronous discrete event simulation systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Christopher D. Carothers , Richard M. Fujimoto, Efficient Execution of Time Warp Programs on Heterogeneous, NOW Platforms, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.299-317, March 2000
	Horst Mehl , Stefan Hammes, How to integrate shared variables in distributed simulation, ACM SIGSIM Simulation Digest, v.25 n.2, p.14-41, Fall 1995
	Jun Wang , Carl Tropper, Optimizing time warp simulation with reinforcement learning techniques, Proceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come, December 09-12, 2007, Washington D.C.
	David W. Bauer Jr. , Christopher D. Carothers , Akintayo Holder, Scalable Time Warp on Blue Gene Supercomputers, Proceedings of the 2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation, p.35-44, June 22-25, 2009

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)
F.1.2 Modes of Computation
Subjects: Parallelism and concurrency

I. Computing Methodologies
I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Performance, Theory

REVIEW

"Osman Balci : Reviewer"

This long theoretical research paper provides a comprehensive and detailed analysis of rollback-based algorithms for parallel discrete event simulation. After an overview of the results, commonly used algorithms for parallel simula more...

Collaborative Colleagues:

Boris Lubachevsky: colleagues

Adam Schwartz: colleagues

Alan Weiss: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player