Stochastic graph transformation systems

Abstract. In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and re-liability 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 appli-cation. Beside the basic definitions and a motivating example, we derive continuous-time Markov chains, establish a link with continuous stochas-tic logic, deal with the problem of abstraction through graph isomor-phisms, and discuss the analysis of properties by means of an experi-mental tool chain.