Stochastic Analysis of Graph Transformation Systems: A Case Study in P2P Networks

  • Reiko Heckel
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and reliability become more and more important. To formalise, measure, and predict these properties, stochastic methods are required. At the same time such systems are characterised by a high degree of architectural reconfiguration. Viewing the architecture of a distributed system as a graph, this is naturally modelled by graph transformations.

To address these two concerns, stochastic graph transformation systems have been introduced associating with each rule its application rate—the rate of the exponential distribution governing the delay of its application. Deriving continuous-time Markov chains, Continuous Stochastic Logic is used to specify reliability properties and verify them through model checking.

In particular, we study a protocol for the reconfiguration of P2P networks intended to improve their reliability by adding redundant connections. The modelling of this protocol as a (stochastic) graph transformation system takes advantage of negative application and conditions path expressions. This ensuing high-level style of specification helps to reduce the number of states and increases the capabilities for automated analysis.


Stochastic Analysis Graph Transformation Atomic Proposition Graph Grammar Injective Morphism 
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.
    Ajmone-Marsan, M., Balbo, G., Conte, G., Donatelli, S., Franceschinis, G.: Modelling with Generalized Stochastic Petri Nets. Wiley Series in Parallel Computing. John Wiley and Sons, Chichester (1995)Google Scholar
  2. 2.
    Anderson, W.G.: Continuous-Time Markov Chains. Springer, Heidelberg (1991)zbMATHGoogle Scholar
  3. 3.
    Baier, C., Haverkort, B.R., Hermanns, H., Katoen, J.-P.: Model checking continuous-time markov chains by transient analysis. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, Springer, Heidelberg (2000)CrossRefGoogle Scholar
  4. 4.
    Bause, F., Kritzinger, P.S.: Stochastic Petri Nets, 2nd edn. Vieweg Verlag (2002)Google Scholar
  5. 5.
    Brinksma, E., Hermanns, H.: Process algebra and Markov chains. In: Brinksma, E., Hermanns, H., Katoen, J.-P. (eds.) EEF School 2000 and FMPA 2000. LNCS, vol. 2090, pp. 183–231. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  6. 6.
    Corradini, A., Montanari, U., Rossi, F.: Graph processes. Fundamenta Informaticae 26(3,4), 241–266 (1996)zbMATHMathSciNetGoogle Scholar
  7. 7.
    D’Argenio, P.R.: Algebras and Automata for Timed and Stochastic Systems. IPA Dissertation Series 1999-10, CTIT PhD-Thesis Series 99-25, University of Twente (November 1999)Google Scholar
  8. 8.
    Ehrig, H., Pfender, M., Schneider, H.J.: Graph grammars: an algebraic approach. In: 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 167–180. IEEE, Los Alamitos (1973)CrossRefGoogle Scholar
  9. 9.
    Gilb, T.: Principles of Software Engineering Management. Addison-Wesley, Reading (1988)zbMATHGoogle Scholar
  10. 10.
    Habel, A., Heckel, R., Taentzer, G.: Graph grammars with negative application conditions. Fundamenta Informaticae 26(3,4), 287–313 (1996)zbMATHMathSciNetGoogle Scholar
  11. 11.
    Heckel, R., Lajios, G., Menge, S.: Stochastic graph transformation systems. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 210–225. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  12. 12.
    Heckel, R., Lajios, G., Menge, S.: Modulare Analyse Stochastischer Graphtransformationssysteme. In: Liggesmeyer, P., Pohl, K., Goedicke, M. (eds.) Software Engineering 2005, Essen, Germany, GI, March 2005. Lecture Notes in Informatics, vol. 64, pp. 141–152 (2005)Google Scholar
  13. 13.
    Korff, M., Ribeiro, L.: Concurrent derivations as single pushout graph grammar processes. In: Proc. Joint COMPUGRAPH/SEMAGRAPH Workshop on Graph Rewriting and Computation (SEGRAGRA). Electronic Notes in TCS, vol. 2, pp. 113–122. Elsevier Science, Amsterdam (1995)Google Scholar
  14. 14.
    Kwiatkowska, M., Norman, G., Parker, D.: PRISM: Probabilistic symbolic model checker. In: Field, T., Harrison, P.G., Bradley, J., Harder, U. (eds.) TOOLS 2002. LNCS, vol. 2324, pp. 200–204. Springer, Heidelberg (2002)Google Scholar
  15. 15.
    Löwe, M.: Algebraic approach to single-pushout graph transformation. Theoret. Comput. Sci. 109, 181–224 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Mariani, L.: Fault-tolerant routing for p2p systems with unstructured topology. In: Proc. International Symposium on Applications and the Internet (SAINT 2005), Trento (Italy). IEEE Computer Society, Los Alamitos (2005)Google Scholar
  17. 17.
    Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. Theoret. Comput. Sci. 96, 73–155 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)zbMATHGoogle Scholar
  19. 19.
    Molloy, M.K.: On the Integration of Delay and Throughput Measures in Distributed Processing Models. PhD thesis, University of California (1981)Google Scholar
  20. 20.
    Natkin, S.: Les Réseaux de Petri Stochastiques et leur Application à l’Evaluation des Systémes Informatiques. PhD thesis, CNAM Paris (1980)Google Scholar
  21. 21.
    Norris, J.R.: Markov Chains. Cambridge University Press, Cambridge (1997)zbMATHGoogle Scholar
  22. 22.
    Priami, C.: Stochastic π-calculus. The Computer Journal 38, 578–589 (1995); Proc. PAPM 1995CrossRefGoogle Scholar
  23. 23.
    Rensink, A.: The GROOVE simulator: A tool for state space generation. In: Pfaltz, J.L., Nagl, M., Böhlen, B. (eds.) AGTIVE 2003. LNCS, vol. 3062, pp. 479–485. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  24. 24.
    Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformation, Foundations, vol. 1. World Scientific, Singapore (1997)Google Scholar
  25. 25.
    Stewart, W.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1994)zbMATHGoogle Scholar
  26. 26.
    University of Paderborn Software Engineering Group. The Fujaba Tool Suite,

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Reiko Heckel
    • 1
  1. 1.Department of Computer ScienceUniversity of LeicesterUnited Kingdom

Personalised recommendations