A causality based time management mechanism for federated simulation

ABSTRACT

One of the six categories of management services provided in the Run Time Infrastructure (RTI) to federated simulations is Time Management. Currently, it provides only two message ordering policies, that is, time stamp ordering and receive ordering. Temporal anomalies occurred during the execution of federation due to the heterogeneous latencies in the communication network are not handled in receive ordering. White time stamp ordering eliminates the temporal anomalies entirely, it incurs great communication latency and huge handwidth requirement. This paper presents a new time management mechanism which provides a less costly message ordering service, namely causal ordering, to federates. It does not require the specification of lookahead and allows federates that do not require stringent message ordering properties to achieve much more efficient execution. A series of experiments has been carried out to benchmark the performance of this new time management mechanism and the results show that if incurs a slight overhead compared to receive ordering mechanism but achieves significant performance improvement over time stamp ordering mechanism.

REFERENCES

• 1: Fast Messages. http:://www-csag.ucsd.edu/projects/comm /fm.html.
• 2: Federated Simulations Development Kit (FDK). Georgia Institute of Technology. http://www.cc.gatech.edu/computing /pads/fdk.html.
• 3: HLA Time Management Design Document, version 1.0. U.S. Department of Defense, August 1996.
• 4: High Level Architecture interface specification, version 1.3. U.S. Department of Defense, April 1998.
• 5: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 6: C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Australian Computer Science Communication, 10(1 ):56-66, February 1988.
• 7: R. Fujimoto. RTI-Kit V0.2 Specification. Georgia Technological University, (18), March 1998.
• 8: Ajay D. Kshemkalyani , Mukesh Singhal, Necessary and sufficient conditions on information for causal message ordering and their optimal implementation, Distributed Computing, v.11 n.2, p.91-111, April 1998 [doi>10.1007/s004460050044]
• 9: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 10: Ravi Prakash , Michel Raynal , Mukesh Singhal, An adaptive causal ordering algorithm suited to mobile computing environments, Journal of Parallel and Distributed Computing, v.41 n.2, p.190-204, March 15, 1997 [doi>10.1006/jpdc.1996.1300 ]
• 11: Michel Raynal , André Schiper , Sam Toueg, The causal ordering abstraction and a simple way to implement it, Information Processing Letters, v.39 n.6, p.343-350, Sept. 27, 1991 [doi>10.1016/0020-0190(91)90008-6 ]
• 12: André Schiper , Jorge Eggli , Alain Sandoz, A New Algorithm to Implement Causal Ordering, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.219-232, September 26-28, 1989
• 13: Chengzheng Sun , Yun Yang , Yanchun Zhang , David Chen, Distributed Concurrency Control in Real-time Cooperative Editing Systems, Proceedings of the Second Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, p.84-95, December 02-05, 1996
• 14: J. Zhou. A causality-based time management mechanism, Master Thesis. August 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Experimentation, Measurement, Performance, Standardization, Theory

Keywords:
causal order delivery, direct dependency, distributed simulation, happen-before relationship, multicasting, time management, time stamp ordering