Stochastic Graph Transformation Systems

• Autorzy: Heckel R. , Lajios G. , Menge S.
• Języki publikacji: EN

Abstrakty

EN

In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and reliability become more and more important. To formalize, measure, and predict such properties, stochastic methods are required. At the same time such systems are characterized by a high degree of architectural reconfiguration. Viewing the architecture of a distributed system as a graph, this is naturally modeled by graph transformations. To combine these two views, in this paper we introduce stochastic graph transformation systems associating with each rule its application rate-the rate of the exponential distribution governing the delay of its application. Beside the basic definitions and a motivating example, we derive continuous time Markov chains, establish a link with continuous stochastic logic, deal with the problem of abstraction through graph isomorphisms, and discuss the analysis of properties by means of an experimental tool chain.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 1
• Strony: 63--84
• Opis fizyczny: bibliogr. 45 poz., wykr.

Twórcy

autor

Heckel R.

autor

Lajios G.

autor

Menge S.

• Department of Computer Science, University of leicester, United Kongdom,

Bibliografia

• [1] M. Ajmone-Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling with Generalized Stochastic Pelri Nels. Wiley Sedes in Parallel Com p u ti n g. John Wiley and Sons, 1995.
• [2] William G. Anderson. Conńnuous-Time Markov Chains. Springer, 1991.
• [3] L. Andrade, P. Baldan, and H. Baumeister. AGILE: Software architecture for mobility. In Recent Trends in Algebraic Develeopment, lóth Intl. Workshop (WADT2002), volume 2755 of Lecture Notes in Computer Science, Frauenchiemsee, 2003. Springer-Verlag.
• [4] Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, and Joost-Pieter Katoen. Model checking continuous-time markovchains by transient analysis. In Computer Aided Yerification, pages 358-372, 2000.
• [5] Falko Bause and Pieter S. Kritzinger. Stochaslic Petń Nets. Yieweg Verlag, 2nd edition, 2002.
• [6] Ed Brinksma and Holger Hermanns. Process algebra and markov chains. In J.-P. Katoen E. Brinksma, H. Hermanns, editor, FMPA 2000, number 2090 in Lecture Notes in Computer Science, pages 183-231. Springer,2001.
• [7] G.A. Churchill. Stochastic models for heterogeneous DNA sequences. Buli. Math. Biol, 51(l):79-94, 1989.
• [8] A. Corradini, U. Montanari, and E Rossi. Graph processes. Fundamenta Informaticae, 26(3,4):241-266, 1996.
• [9] A. Corradini, L. Ribeiro, and F.L. Dotli. A graph transformation view on the specification of applications using mobile code. In G. Taentzer L. Baresi, M. Pezze and C. Zaroliagis, editors, Proceedings 2nd Int. Workshop on Craph Transformation and Visual Modeling Teclmique {GT-YMT 01), volume 50.3 of Elect. Notes in Th. Comput. Sci. El sevier Science, 2001.
• [10] P.R. D'Argenio. Algebras and Automata for Timed and Stochastic Systems. IPA Dissertation Series 1999-10. CTIT PhD-Thesis Series 99-25, University of Twente, November 1999.
• [11] J. Diederich, L. Wolf, and M. Zitterbart. A mobile differentiated services QoS model. In Proceedings of the 3rd Workshop on Applications and Services in Wireless Networks, 2003.
• [12] H. Ehrig and B. Mahr. Fundamentalsof algebraic specifications l: Equations and initial semantics, volume 6 of EACTS Monographs on Theoretical Computer Science. Springer, Berlin, 1985.
• [13] H. Ehrig, M. Pfender, and H.J. Schneider. Graph grammars: an algebraic approach. In I4th Annual IEEE Symposium on Switching and Automata Theory, pages 167-180. IEEE, 1973.
• [14] Hartmut Ehrig, Annegret Habel, Julia Padberg, and Ulrike Prange. Adhesive high-level replacement cate-gories and systems. In Hartmut Ehrig, editor, Proceedings of the Second International Conference on Graph Transformations, volume 3256 of Lecture Notes in Computer Science, pages 144-160. Springer, 2004.
• [15] Hartmut Ehrig, Ulrike Prange, and Gabriele Taentzer. Fundamental theory for typed attributed graph transformation. In Hartmut Ehrig, editor, Pmceedings ofthe Second International Conference on Graph Transformations, volume 3256 of Lecture Notes in Computer Science, pages 161-177, 2004.
• [16] F. Gadducci and U. Montanari. A concurrent graph semantics for mobile ambients. In St. Brooks and M. Mislove, editors, Proc. Mathematical Foundations of Programming Semantics, Aarhus, volume 45 of Elect. Notes in Th. Comput. Sci. El sevier Science, 2001.
• [17] T. Gilb. Principles of Software Engineering Management. Addison-Wesley. 1988.
• [18] P. Guoand., R. Heckei. Conceptual modellingof styles for mobile systems: A layered approach based on graph transformation. In Proc. IFIP TCS Working Conference on Mobile Information Systems, Oslo, Norway, pages 65-78,2004.
• [19] A. Habel, R. Heckei, and G. Taentzer. Graph grammars with negative application conditions. Fundamenta Informaticae, 26(3,4):287 - 313, 1996.
• [20] Reiko Heckei, Georgios Lajios, and Sebastian Menge. Stochastic graph transformation. In Proceedings of the 2nd International Conference on Graphtransformation, ICGT '04, Lecture Notes in Computer Science, 2004.
• [21] H. Hermanns, J. P. Katoen, J. Meyer-Kayser, and M. Siegle. A tool for model checking markov chains. Software Tools for Technology Transfer, 2002.
• [22] D. Hirsch and U. Montanari. Consistent transformat i on s for software architecture styles of distributed sys-tems. In G. Stefanescu, editor, Workshop on Distributed Systems, volume 28 of Electronic Notes in TCS, 1999.
• [23] Leonard Kleinrock. Queueing Systems, Volume I: Theoiy. Wiley-Interscince, 1975.
• [24] M. Kwiatkowska, G. Norman, and D. Parker. PRISM: Probabilistic symbolic model checker. In T. Field, P. Harrison, J. Bradley, and U. Harder, editors, Proc. I2th Int. Conf. on Modelling Techniąues and Tools for Computer Performance Evaluation (TOOLS'02), volume 2324 of Lecture Notes in Computer Science, pages 200-204. Springer, April 2002.
• [25] K. Lari and S.J. Young. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 4:35-56. 1990.
• [26] R. Milner. Communication an d Concurrency. Prentice-Hall, 1989.
• [27] M. K. Molloy. On the Integration of Delay and Throiighput Measures in Distributed Processing Models. PhD thesis, University of California, 1981.
• [28] M. Mosbah. Probabilistic graph grammars. Fundamenta Informaticae, vol. 26:pp. 341-360, 1996.
• [29] S. Natkin. Les Reseaux de Petri Slochastigues et leur Application l'Evaluation des Systemes Informatigues. PhD thesis, CNAM Paris, 1980.
• [30] James R. Norris. Markov Chains. Cambridge University Press, 1997.
• [31] Tim Oates, Shailesh Doshi, and Fang Huang. Estimating maximum likelihood parameters for stochastic context-free graph grammars. In Inductve Logic Programming: !3th International Conference, ILP 2003, pages 281-298, 2003.
• [32] CorradoPriami. Stochastic π-calculus. Computer Journal, 38(7):578-589, 1995.
• [33] Lawrence R. Rabiner. A tulorial on hidden Markov models and selected applications in speech recognition, pages 267-296. Morgan Kaufmann Publishers Inc., 1990.
• [34] A. Rensink. The GROOYE simulator: A tool for stale space generation. In J.L. Pfaltz, M. Nagi, and B. Bohlen, editors, Applications of Graph Transformation with Induslrial Relevance Proc. 2nd Intl. Workshop ACTIVE'03. Charloltesville, USA, 2003, volume 3062 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2004.
• [35] F. Rossell"o and G. Yaliente. Graph transformation in molecular biology. In H.-J. Kreowski, U. Montanari, F. Orejas, G. Rozenberg, and G. Taentzer, editors, Formal Metliods in Software and System Modeling, volume 3393 of Lecture Notes in Computer Science, pages 116-133. Springer, 2005.
• [36] G. Rozenberg, editor. Handbook on Graph Grammars: Foundations, volume l. World Scientific, Singapore, 1997.
• [37] Akos Schmidt and Daniel Varró. CheckYML: A tool for model checking visual modeling languages. In Perdita Stevens, Jon Whittle, and Grady Booch, editors, UML 2003 - The Unified Modeling Language. Model Languages and Applications. 6th International Conference, San Francisco, CA, USA, October 2003. Proceedings, volume 2863 of Lecture Notes in Computer Science, pages 92-95. Springer, 2003.
• [38] Andy Schürr. PROGRES: a VHL-language based on graph grammars. In Proc. 4th Int. Workshop on Graph-Grammars and Their Application to Computer Science, number 532 in Lecture Notes in Computer Science, pages 641-659. Springer-Verlag, 1991
• [39] Baozhen Shan. Stochastic context-free graph grammars for glycoprotein modelling. In CIAA, pages 247-258. 2004.
• [40] W. Stewart. Introduction to the Nitmerical Solution of Markov Chains. Princeton University Press, 1994.
• [41] G. Taentzer. Hierarchically distributed graph transformation. In 5th Int. Workshop on Graph Grammars and iheir Application to Computer Science, Williamsburg '94, LNCS 1073, pages 304 - 320, 1996.
• [42] Gabriele Taentzer. AGG: A graph transformation environment for modeling and validation of software. In John L. Pfaltz, Manfred Nagi, and Boris Bohlen, editors, Applications of Graph Transformations with Industrial Relevance, Second International Workshop, number 3062 in Lecture Notes in Computer Science, pages 446-453, 2004.
• [43] Daniel Varró. Automated formal verification of visual modeling languages by model checking. Journal of Software and Systems Modelling, 2003. Accepted to the Special Issue on Graph Transformation and Yisual Modelling Techniques.
• [44] Oliver T. W. Yu and Victor C. M. Leung. Adaptive resource allocation for prioritized cali admission over an ATM-based wireless PCN. IEEE Journal on Selected Areas in Communications, 15:1208-1224,1997.
• [45] M. Zonoozi and P. Dassanayake. User mobility modeling and characterization of mobility patterns. IEEE Journal on Selected Areas in Communications, 15:1239-1252, 1997.