Article

Causality information and fossil collection in timewarp simulations

Authors:

Malolan Chetlur,

Philip A. WilseyAuthors Info & Claims

WSC '06: Proceedings of the 38th conference on Winter simulation

Pages 987 - 994

Published: 03 December 2006 Publication History

Abstract

This paper presents a Time Warp fossil collection mechanism that functions without need for a GVT estimation algorithm. Effectively each Logical Process (LP) collects causality information during normal event execution and then each LP utilizes this information to identify fossils. In this mechanism, LPs use constant size vectors (that are independent of the total number of parallel simulation objects) as timestamps called Plausible Total Clocks to disseminate causality information. For proper operation, this mechanism requires that the communication layer preserves a FIFO ordering on messages. A detailed description of this new fossil collection mechanism and its proof of correctness is presented in this paper.

References

[1]

Bellenot, S. 1990, January. Global virtual time algorithms. In Distributed Simulation, 122--127. Society for Computer Simulation.

[2]

Charron-Bost, B. 1991, July. Concerning the size of logical clocks in distributed systems. Information Processing Letters 39 (1): 11--16.

Digital Library

[3]

Chetlur, M. 2001, May. Causality representation and cancellation mechanism in timewarp simulations. In 12th Workshop on Parallel and Distributed Simulation. Society for Computer Simulation.

Digital Library

[4]

D'Souza, L. M., X. Fan, and P. A. Wilsey. 1994, July. pGVT: An algorithm for accurate GVT estimation. In Proceedings of the 8th Workshop on Parallel and Distributed Simulation (PADS 94), 102--109. Society for Computer Simulation.

Digital Library

[5]

Fujimoto, R. 1990, October. Parallel discrete event simulation. Communications of the ACM 33 (10): 30--53.

Digital Library

[6]

Fujimoto, R. 1993. Parallel and distributed discrete event simulation: algorithms and applications. In Proceedings of the 1993 Winter Simulation Conference, 106--114.

Digital Library

[7]

Fujimoto, R. M., and M. Hybinette. 1994, August. Computing global virtual time in shared-memory multiprocessors. ACM Transactions on Modeling and Computer Simulation 7(4):425--446.

Digital Library

[8]

Jefferson, D. 1985, July. Virtual time. ACM Transactions on Programming Languages and Systems 7 (3): 405--425.

Digital Library

[9]

Jefferson, D. 1990. Virtual time II: storage management in conservative and optimistic systems. In Proceedings of the 9th Annual Symposium on Principles of Distributed Computing, 75--89. ACM Press, New York, NY.

Digital Library

[10]

Lamport, L. 1978, July. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21 (7): 558--565.

Digital Library

[11]

Lin, Y.-B., and E. Lazowska. 1990. Determining the global virtual time in a distributed simulation. In 1990 International Conference on Parallel Processing, III-201-III-209.

[12]

Mattern, F. 1993, August. Efficient algorithms for distributed snapshots and global virtual time approximation. Journal of Parallel and Distributed Computing 18 (4): 423--434.

Digital Library

[13]

Nicol, D. 1996, December. Principles of conservative parallel simulation. In Proceedings of the 1996 Winter Simulation Conference (WSC 96), 128--135.

Digital Library

[14]

Radhakrishnan, R., T. J. McBrayer, K. Subramani, M. Chetlur, V. Balakrishnan, and P. A. Wilsey. 1996, March. A comparative analysis of various time warp algorithms implemented in the WARPED simulation kernel. In Proceedings of the 29th Annual Simulation Symposium, 107--116.

Digital Library

[15]

Raynal, M., and M. Singhal. 1996, February. Logical time: Capturing causality in distributed systems. IEEE Computer:49--56.

Digital Library

[16]

Tel, G. 1991. Topics in distributed algorithms. Cambridge Universiy Press.

Digital Library

[17]

Tomlinson, A. I., and V. K. Garg. 1993, July. An algorithm for minimally latent global virtual time. In Proceedings of the 7th Workshop on Parallel and Distributed Simulation (PADS), 35--42. Society for Computer Simulation.

Digital Library

[18]

Torres-Rojas, F. J., and M. Ahamad. 1996. Plausible clocks: constant size logical clocks for distributed systems. In Workshop on Distributed Algorithms, 71--88.

Digital Library

[19]

Xiao, Z., B. Unger, R. Simmonds, and J. Cleary. 1999. Scheduling critical channels in conservative parallel discrete event simulation. In Proceedings of the Thirteenth Workshop on Parallel and Distributed Simulation (PADS '99), 20--28. Washington, DC, USA: IEEE Computer Society.

Digital Library

[20]

Young, C. H., N. B. Abu-Ghazaleh, and P. A. Wilsey. 1998, September. OFC: a distributed fossil-collection algorithm for time-warp. In 12th International Symposium on Distributed Computing, (DISC'98, formerly WDAG).

Digital Library

Cited By

Pellegrini AQuaglia FTaylor SMustafee NSon Y(2015)NUMA Time WarpProceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2769458.2769479(59-70)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1145/2769458.2769479
Liu QWainer G(2009)A Performance Evaluation of the Lightweight Time Warp Protocol in Optimistic Parallel Simulation of DEVS-Based Environmental ModelsProceedings of the 2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2009.15(27-34)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.1109/PADS.2009.15

Recommendations

Optimistic Fossil Collection for Time Warp Simulation
HICSS '96: Proceedings of the 29th Hawaii International Conference on System Sciences Volume 1: Software Technology and Architecture

Optimistic Fossil Collection is a fully distributed mechanism to reclaim memory from the state and event histories of a Time Warp simulation. Each fossil collector executes with a Logical Process (LP) and operates independently of other fossil ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Causality representation and cancellation mechanism in time warp simulations
PADS '01: Proceedings of the fifteenth workshop on Parallel and distributed simulation

The Time Warp synchronization protocol allows causality errors and then recovers from them with the assistance of a cancellation mechanism. Cancellation can cause the rollback of several other simulation objects that may trigger a cascading rollback ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '06: Proceedings of the 38th conference on Winter simulation

December 2006

2429 pages

ISBN:1424405017

Editors:
L. Felipe Perrone
Bucknell University
,
Barry G. Lawson
University of Richmond
,
Jason Liu
Colorado School of Mines
,
Frederick P. Wieland
Sensis Corporation
,
General Chair:
David Nicol
University of Illinois, Urbana-Champaign
,
Program Chair:
Richard Fujimoto
College of Computing, Georgia Tech

Sponsors

IIE: Institute of Industrial Engineers
ASA: American Statistical Association
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE-CS\DATC: The IEEE Computer Society
SIGSIM: ACM Special Interest Group on Simulation and Modeling
NIST: National Institute of Standards and Technology
(SCS): The Society for Modeling and Simulation International
INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

Publisher

Winter Simulation Conference

Publication History

Published: 03 December 2006

Check for updates

Qualifiers

Article

Conference

WSC06

Sponsor:

IIE
ASA
IEICE ESS
IEEE-CS\DATC
SIGSIM
NIST
(SCS)
INFORMS-CS

WSC06: Winter Simulation Conference 2006

December 3 - 6, 2006

California, Monterey

Acceptance Rates

WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
105
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pellegrini AQuaglia FTaylor SMustafee NSon Y(2015)NUMA Time WarpProceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2769458.2769479(59-70)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1145/2769458.2769479
Liu QWainer G(2009)A Performance Evaluation of the Lightweight Time Warp Protocol in Optimistic Parallel Simulation of DEVS-Based Environmental ModelsProceedings of the 2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2009.15(27-34)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.1109/PADS.2009.15

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten