Clustering in Stochastic Asynchronous Algorithms for Distributed Simulations

  • Anatoli Manita
  • François Simonot
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


We consider a cascade model of N different processors performing a distributed parallel simulation. The main goal of the study is to show that the long-time dynamics of the system have a cluster behaviour. To attack this problem we combine two methods: stochastic comparison and Foster–Lyapunov functions.


Markov Chain Lyapunov Function Tangent Line Cascade Model Queueing Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Jefferson, D., Witkowski, A.: An Approach to Performance Analysis of Time stamp-driven Synchronization Mechanisms, ACM0-89791-143-1 84, 008/0243 (1984)Google Scholar
  2. 2.
    Mitra, D., Mitrani, I.: Analysis and Optimum performance of two message-passing parallel processors synchronized by rollback. Performance Evaluation 7, 111–124 (1987)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Madisetti, V.K., Walrand, J.C., Messerschmitt, D.G.: Asynchronous Algorithms for the ParaSimulation of Event-Driven Dynamical Systems. ACM Transactions on Modelling and Computer Simulation 1(3), 244–274 (1991)zbMATHCrossRefGoogle Scholar
  4. 4.
    Gupta, A., Akyildiz, I.F., Fujimoto, R.M.: Performance Analysis of Time Warp With Multiple Homogeneous Processors. IEEE Transactions On Software Engineering 17(10), 1013 (1991)CrossRefGoogle Scholar
  5. 5.
    Akyildiz, I.F., Chen, L., Dast, S.R., Fujimoto, R.M., Serfozo, R.F.: Performance Analysis of Time Warp with Limited Memory. Performance Evaluation Review 20(1) (June 1992)Google Scholar
  6. 6.
    Kumar, A., Shorey, R.: Stability of Event Synchronisation in Distributed Discrete Event Simulation. In: Proc. of the eighth workshop on parallel and distributed simulation, Edinburgh, Scotland, United Kingdom, pp. 65–72 (1994)Google Scholar
  7. 7.
    Fayolle, G., Malyshev, V., Menshikov, M.: Topics on constructive countable Markov chains. Cambridge University Press, Cambridge (1995)Google Scholar
  8. 8.
    Yu Popov, S., Greenberg, A.G., Malyshev, V.A.: Stochastic models of massively parallel computation. Markov Processes and Related Fields 1(4), 473–490 (1995)zbMATHMathSciNetGoogle Scholar
  9. 9.
    Greenberg, A.G., Shenker, S., Stolyar, A.L.: Asynchronous Updates in Large Parallel Systems. SIGMETRICS 96 5/96 PA, USAGoogle Scholar
  10. 10.
    Gupta, M., Kumar, A., Shorey, R.: Queueing Models and Stability of Message Flows in Distributed Simulators of Open Queueing Networks. In: Proc. of the tenth workshop on parallel and distributed simulation, Philadelphia, Pennsylvania, United States, pp. 162–169 (1996)Google Scholar
  11. 11.
    Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont (1997)Google Scholar
  12. 12.
    Shorey, R., Kumar, A., Rege, K.M.: Instability and Performance Limits of Distributed Simulators of Feedforward Queueing Networks. ACM Transactions on Modeling and Computer Simulation 7(2), 210–238 (1997)zbMATHCrossRefGoogle Scholar
  13. 13.
    Gupta, M., Kumar, A.: A Nonblocking Algorithm for the Distributed Simulation of FCFS Queueing Networks with Irreducible Markovian Routing. In: Proc. of the twelfth workshop on parallel and distributed simulation, Banff, Alberta, Canada, pp. 20–27 (1998)Google Scholar
  14. 14.
    Voznesenskaya, T.V.: Analysis of algorithms of time synchronisation for distributed simulation. Artificial intelligence (Donetsk) 2, 24–30 (2000) (in Russian) Google Scholar
  15. 15.
    Voznesenskaya, T.V.: Mathematical model of algorithms of synchronization of time for the distributed simulation. In: Korolev, L.N. (ed.) “Program systems and tools”: the Thematic collection of faculty VMiK of the Moscow State University N1, pp. 56–66. MAX Press (2000)Google Scholar
  16. 16.
    Malyshev, V., Manita, A.: Time synchronization problem. Rapport de recherche INRIA, 5204 (2004)Google Scholar
  17. 17.
    Manita, A., Shcherbakov, V.: Asymptotic analysis of particle system with mean-field interaction, arXiv:math.PR/0408372 (2004),
  18. 18.
    Malyshev, V.A., Manita, A.D.: Phase transitions in the time synchronization model. Probability Theory and Applications 50, 150–158 (2005)MathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Anatoli Manita
    • 1
  • François Simonot
    • 2
  1. 1.Faculty of Mathematics and MechanicsMoscow State UniversityMoscowRussia
  2. 2.IECNUniversité Henri Poincaré Nancy I, EsstinVandoeuvreFrance

Personalised recommendations