article

An alternative time management mechanism for distributed simulations

Authors:

Stephen J. Turner,

Junlan ZhouAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 15, Issue 2

Pages 109 - 137

https://doi.org/10.1145/1060576.1060577

Published: 01 April 2005 Publication History

Abstract

Over the past few years, there has been a keen interest in the management of time in distributed simulation environments. Previous emphasis in time management (TM) services has been based on time stamp ordering, which is both computation and bandwidth intensive. This article discusses an alternative approach to time management based on causal ordering. Traditional causal ordering protocols incur a large amount of communication overhead, which is generally of the order of N² for a distributed system of N processes. A new causal ordering protocol proposed by the authors, the Modified Schiper-Eggli-Sandoz (MSES) protocol, is presented in this article. This new protocol minimizes the control information overhead of causal ordering by using the direct dependency tracking technique. The MSES protocol works well in both unicast and multicast environments, without relying on information about the underlying network topology and communication pattern among the processes of the distributed system. The MSES protocol has been successfully implemented as a middleware on top of DMSO RTI. Experiments have been conducted to benchmark the performance of the new time management mechanism with respect to the existing TM mechanisms available in DMSO RTI. The simulation scenarios of the experiments vary with different degrees of inter-federate dependency and federate event granularities. The ordering limitations of the causality based TM mechanism are addressed in this article and the trade-off of the degree of event ordering and execution speed of simulations is discussed.

References

[1]

Ahamad, M., Hutto, P. W., Neiger, G., Burns, J. E., and Kohli, P. 1993. Causal Memory: Definitions, Implementation and Programming. Tech. Rep. 93/55, College of Computing, Georgia Institute of Technology. September.

[2]

Birman, K., Schiper, A., and Stephenson, P. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9, 3 (August), 272--314.

[3]

FDK. 1998. Federated Simulations Development Kit (FDK), Georgia Institute of Technology.

[4]

Fidge, C. J. 1988. Timestamps in Message-passing systems that preserve the partial ordering. Austral. Comput. Sci. Comm. 10, 1 (February), 56--66.

[5]

Fujimoto, R. M. 1998. Time management in the high level architecture. Simulation 71, 6 (December), 388--400.

[6]

Fujimoto, R. M. 2000. Parallel and Distributed Simulation Systems. Wiley Book Series on Parallel and Distributed Computing. Wiley.

[7]

Fujimoto, R. M. and Weatherly, R. M. 1996. Time management in the DoD high level architecture. In Proceedings of 10th Workshop on Parallel and Distributed Simulation (PADS 96). 60--67.

[8]

Fullford, D. and Wetzel, D. 1999. A federation management tool: Using the management object model (MOM) to manage, control, and monitor a federation. In Proceedings of the 1999 Spring Simulation Interoperability Workshop. Number 99S-SIW-196.

[9]

IEEE Standard 1278. 1993. IEEE 1278, Standard for Information Technology---Protocols for Distributed Interactive Simulation Applications.

[10]

IEEE Standard 1516. 2000. IEEE 1516, Standard for Modeling and Simulation (M&S) High Level Architecture.

[11]

Kshemkalyani, A. D. and Singhal, M. 1998. Necessary and sufficient conditions on information for causal message ordering and their optimal implementation. Distributed Computing 11, 2, 91--111.

[12]

Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7, 558--565.

[13]

Lee, B. S., Cai, W., and Zhou, J. 2001. A causality based time management mechanism for federated simulation. In Proceedings of the 15th Workshop on Parallel and Distributed Simulation (PADS 2001). 83--90.

[14]

Mattern, F. 1989. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel and Distributed Algorithms, M. Cosnard et al., Eds. Elsevier Science Publishers B. V., 215--226.

[15]

Prakash, R., Raynal, M., and Singhal, M. 1997. An adaptive causal ordering algorithm suited to mobile computing environments. J. Para. Distrib. Comput. 41, 190--204.

[16]

Raynal, M., Schiper, A., and Toueg, S. 1991. The causal ordering abstraction and a simple way to implement it. Info. Proc. Letters 39, 6, 343--350.

[17]

Schiper, A., Eggli, J., and Sandoz, A. 1989. A new algorithm to implement causal ordering. In Proceedings of the Workshop on Distributed Algorithms LNCS 392, 219--232.

[18]

Singhal, M. and Kshemkalyani, A. 1992. An efficient implementation of vector clocks. Info. Proc. Letters 43, 1 (August), 47--52.

[19]

Sun, C., Zhang, Y., Yang, Y., and Chen, C. 1996. Distributed concurrency control in real-time cooperative editing systems. In Proceedings of the 1996 Asian Computing Science Conference. 84--95.

[20]

Turner, S. J., Cai, W., and Chen, J. 2003. A middleware approach to causal order delivery in distributed simulations. In Proceedings of the 2003 European Simulation Interoperability Workshop (Euro-SIW). Number 03E-SIW-085.

[21]

Wilson, A. L. and Weatherly, R. M. 1994. The aggregate level simulation protocol: An evolving system. In Proceedings of the 1994 Winter Simulation Conference. 781--787.

[22]

Yavatkar, R. 1992. MCP: A protocol for coordination and temporal synchronization in multimedia collaborative applications. In Proceedings of the 12th IEEE International Conference on Distributed Computer Systems. 603--613.

[23]

Zhou, J. 2000. A Causality Based Time Management Mechanism. M.Eng. thesis, Nanyang Technological University, Singapore.

Cited By

Lv YZhang W(2017)A relevant casual relation based timestamp order consistency control method in DVE systems2017 IEEE 3rd Information Technology and Mechatronics Engineering Conference (ITOEC)10.1109/ITOEC.2017.8122381(1-5)Online publication date: Oct-2017
https://doi.org/10.1109/ITOEC.2017.8122381
Pellegrini APeluso SQuaglia FVitali R(2016)Transparent Speculative Parallelization of Discrete Event Simulation Applications Using Global VariablesInternational Journal of Parallel Programming10.1007/s10766-016-0429-244:6(1200-1247)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s10766-016-0429-2
Pellegrini AQuaglia F(2014)The ROme OpTimistic Simulator: A TutorialEuro-Par 2013: Parallel Processing Workshops10.1007/978-3-642-54420-0_49(501-512)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54420-0_49
Show More Cited By

Index Terms

An alternative time management mechanism for distributed simulations
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Distributed simulation

Recommendations

Broadcast Time Warp
HICSS '95: Proceedings of the 28th Hawaii International Conference on System Sciences

In many distributed computations, it is necessary to ensure that the causal order in which events occur (a partial order) conforms to a total order that is derived from a correctness constraint on the computation. For example, the events of a ...
Using Computational Reflection in Optimistic Distributed Simulations
SCCC '99: Proceedings of the 19th International Conference of the Chilean Computer Science Society

The recent studies in the distributed simulation area are focused in the High Level Architecture, defined by the DoD/USA, which proposes a standard environment to develop and run distributed simulations. The HLA components are designed to ensure a high ...
An Approach for the Unified Time Management Mechanism for HLA

The High Level Architecture (HLA) is the IEEE 1516 standard to model and design a distributive simulation environment. It establishes a common distributed simulation framework, which facilitates the interoperability and reuse of simulation components. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 15, Issue 2

April 2005

66 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/1060576

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2005

Published in TOMACS Volume 15, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
1,217
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lv YZhang W(2017)A relevant casual relation based timestamp order consistency control method in DVE systems2017 IEEE 3rd Information Technology and Mechatronics Engineering Conference (ITOEC)10.1109/ITOEC.2017.8122381(1-5)Online publication date: Oct-2017
https://doi.org/10.1109/ITOEC.2017.8122381
Pellegrini APeluso SQuaglia FVitali R(2016)Transparent Speculative Parallelization of Discrete Event Simulation Applications Using Global VariablesInternational Journal of Parallel Programming10.1007/s10766-016-0429-244:6(1200-1247)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s10766-016-0429-2
Pellegrini AQuaglia F(2014)The ROme OpTimistic Simulator: A TutorialEuro-Par 2013: Parallel Processing Workshops10.1007/978-3-642-54420-0_49(501-512)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54420-0_49
Dong WLoper MWainer G(2013)A time management optimization framework for large-scale distributed hardware-in-the-loop simulationProceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2486092.2486126(265-276)Online publication date: 19-May-2013
https://dl.acm.org/doi/10.1145/2486092.2486126
Santoro AQuaglia F(2012)Transparent optimistic synchronization in the high-level architecture via time-management conversionACM Transactions on Modeling and Computer Simulation10.1145/2379810.237981422:4(1-26)Online publication date: 21-Nov-2012
https://dl.acm.org/doi/10.1145/2379810.2379814
Chen CJia H(2012)Vector Time Management Based on Topology Information for HLA/RTIProceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2012.47(78-80)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1109/PADS.2012.47
ZHANG WZHOU HPENG YLI S(2010)Asynchronous Time Consistency Control Methods in Distributed Interactive SimulationJournal of Software10.3724/SP.J.1001.2010.0363021:6(1208-1219)Online publication date: 29-Jun-2010
https://doi.org/10.3724/SP.J.1001.2010.03630
Mustafee NTaylor SKatsaliaki KBrailsford S(2009)Facilitating the Analysis of a UK National Blood Service Supply Chain Using Distributed SimulationSimulation10.1177/003754970810053085:2(113-128)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1177/0037549708100530
Tang XCai W(2009)Communication-Efficient Support for Spatial Filtering of State Updates in Distributed Virtual EnvironmentsProceedings of the 2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2009.13(129-136)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.1109/PADS.2009.13
Zhang WZhou HPeng YLi S(2009)Providing Responsiveness Requirement Based Consistency in DVEProceedings of the 2009 15th International Conference on Parallel and Distributed Systems10.1109/ICPADS.2009.52(594-601)Online publication date: 8-Dec-2009
https://dl.acm.org/doi/10.1109/ICPADS.2009.52
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents