Stochastic Graph Transformation Systems

Issue title: SPECIAL ISSUE ON ICGT 2004

Article type: Research Article

Authors: Heckel, Reiko | Lajios, Georgios | Menge, Sebastian

Affiliations: Department of Computer Science University of Leicester, United Kingdom. E-mail: reiko@mcs.le.ac.uk | Software-Technology University of Dortmund, Germany

Abstract: 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.

Journal: Fundamenta Informaticae, vol. 74, no. 1, pp. 63-84, 2006