Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In conservative distributed simulation systems, data synchronization can be achieved by using time stamps or causality tracking. Message ordering techniques based on time-stamps usually cause serious performance problems by impeding possible concurrency. On the other hand, causality based methods introduces minimal delay on message processing but requires large control information to be appended to messages. Both transmission and handling of control information are drawbacks of such methods.

In this study, two causality based message ordering algorithms MSES (Modified Schipper-Egglie-Sandoz) and KS (Kshemkalyani-Singhal) are studied. The algorithms are implemented and tested on a common simulation environment. Both theoretical and experimental analysis and comparison of the algorithms are presented.

REFERENCES

• 1: 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]
• 2: Wentong Cai , Stephen J. Turner , Bu-Sung Lee , Junlan Zhou, An alternative time management mechanism for distributed simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.2, p.109-137, April 2005 [doi>10.1145/1060576.1060577]
• 3: Punit Chandra , Pranav Gambhire , Ajay D. Kshemkalyani, Performance of the Optimal Causal Multicast Algorithm: A Statistical Analysis, IEEE Transactions on Parallel and Distributed Systems, v.15 n.1, p.40-52, January 2004 [doi>10.1109/TPDS.2004.1264784]
• 4: Richard M. Fujimoto , Richard M. Weatherly, Time management in the DoD high level architecture, Proceedings of the tenth workshop on Parallel and distributed simulation, p.60-67, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/238788.238817]
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: 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

INDEX TERMS

Keywords:
Kshemkalyani-Singhal algorithm, MSES, causal order algorithms, distributed simulation, time management