Wentong Cai
Stephen J. Turner
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 N2 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.
- 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.Google Scholar
- Birman, K., Schiper, A., and Stephenson, P. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9, 3 (August), 272--314. Google Scholar
- FDK. 1998. Federated Simulations Development Kit (FDK), Georgia Institute of Technology.Google Scholar
- Fidge, C. J. 1988. Timestamps in Message-passing systems that preserve the partial ordering. Austral. Comput. Sci. Comm. 10, 1 (February), 56--66.Google Scholar
- Fujimoto, R. M. 1998. Time management in the high level architecture. Simulation 71, 6 (December), 388--400.Google Scholar
- Fujimoto, R. M. 2000. Parallel and Distributed Simulation Systems. Wiley Book Series on Parallel and Distributed Computing. Wiley. Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- IEEE Standard 1278. 1993. IEEE 1278, Standard for Information Technology---Protocols for Distributed Interactive Simulation Applications.Google Scholar
- IEEE Standard 1516. 2000. IEEE 1516, Standard for Modeling and Simulation (M&S) High Level Architecture.Google Scholar
- 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. Google Scholar
- Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7, 558--565. Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- Singhal, M. and Kshemkalyani, A. 1992. An efficient implementation of vector clocks. Info. Proc. Letters 43, 1 (August), 47--52. Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- Zhou, J. 2000. A Causality Based Time Management Mechanism. M.Eng. thesis, Nanyang Technological University, Singapore.Google Scholar
Index Terms
- An alternative time management mechanism for distributed simulations
Recommendations
Broadcast Time Warp
HICSS '95: Proceedings of the 28th Hawaii International Conference on System SciencesIn 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 SocietyThe 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. ...
Reviews
Dik Kettenis
High-level architecture (HLA) provides an architecture supporting simulations executed at geographically distributed locations. In such simulations, heterogeneous delays associated with modeling computations and message transmissions over the network may lead to temporal anomalies. (An example given by the authors is that of an observer seeing a tank destroyed before it was hit by an aircraft.) Therefore, time management is an important issue in distributed simulations. The authors have designed and implemented a new message ordering scheme (called causal order) in which the cause and effect relationships among events are captured, and message delivery to a component according to those relationships is ensured. In this paper, the authors define the scheme, and describe the software architecture of the implementation. The paper concludes with some results of experiments, showing that the new causal ordering scheme outperforms two other HLA time management schemes. The paper provides a clear presentation of the subject matter, and can be read without a solid background in HLA. Some software engineering concepts are used without any explanation or reference, including the class diagram (it is not even indicated that it is a unified modeling language (UML) class diagram), vector class, inheritance, and overridden methods. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments