Process Evolution based on Transformation of Algebraic High-Level Nets with Applications to Communication Platforms Electronic Communications of the EASST Volume 51 (2012) Proceedings of the 5th International Workshop on Petri Nets, Graph Transformation and other Concurrency Formalisms (PNGT 2012) Process Evolution based on Transformation of Algebraic High-Level Nets with Applications to Communication Platforms Karsten Gabriel 12 pages Guest Editors: Julia Padberg, Kathrin Hoffmann Managing Editors: Tiziana Margaria, Julia Padberg, Gabriele Taentzer ECEASST Home Page: http://www.easst.org/eceasst/ ISSN 1863-2122 http://www.easst.org/eceasst/ ECEASST Process Evolution based on Transformation of Algebraic High-Level Nets with Applications to Communication Platforms Karsten Gabriel kgabriel@cs.tu-berlin.de, Technische Universität Berlin Abstract: Algebraic High-Level (AHL) nets are a well-known modelling technique based on Petri nets with algebraic data types, which allows to model the communi- cation structure and the data flow within one modelling framework. Transformations of AHL-nets – inspired by the theory of graph transformations – allow in addition to modify the communication structure. Moreover, high-level processes of AHL-nets capture the concurrent semantics of AHL-nets in an adequate way. In this paper we show how to model the evolution of communication platforms and scenarios based on transformations of algebraic high-level nets and processes. All constructions and results are illustrated by a running example showing the evolution of Apache Wave platforms and scenarios. The evolution of platforms is modelled by the transforma- tion of AHL-nets and that of scenarios by the transformation of AHL-net processes. Our main result is a construction for the evolution of AHL-processes based on the evolution of the corresponding AHL-net. This result can be used to transform sce- narios in a communication platform according to the evolution of possibly multiple actions of the platform. Keywords: High-Level Nets, Processes, Transformation, Communication Platforms 1 Introduction High-level nets based on low-level Petri nets [Roz87, Rei85] and data types in the program- ming language ML have been studied as coloured Petri nets by Jensen [Jen91] and – using algebraic data types – as algebraic high-level (AHL) nets in [Rei90, PER95]. Inspired by the theory of graph transformations [Ehr79, Roz97] transformations of AHL-nets were first stud- ied in [PER95] which – in addition to the token game – also allow to modify the net structure by rule based transformations. The concept of processes in Petri nets is essential to model not only sequential, but especially concurrent firing behaviour. High-level processes for algebraic high-level nets, called AHL-net processes, have been introduced in [EHP+02, Ehr05], which are high-level net morphisms p : K → AN with AN being an AHL-net, based on a suitable concept of high-level occurrence nets K. The main aim of this paper is to give a short introduction to the integrated framework of transformations of algebraic high-level nets and processes and to show how this can be applied to modern communication platforms. In Section 2 we introduce a small case study of an Apache Wave platform, which is also used as running example for the following sections. In Section 3 we introduce AHL-nets together with high-level processes in the sense of [Ehr05]. Rule based transformations in analogy to graph 1 / 12 Volume 51 (2012) mailto:kgabriel@cs.tu-berlin.de Process Evolution based on Transformation of Algebraic High-Level Nets transformation systems [Roz97] are introduced in Section 4 for AHL-nets and AHL-processes and applied to the evolution of Apache Wave communication platforms and waves. Our main result presented in Section 4 shows how AHL-net processes can be transformed based on a special kind of transformation for AHL-nets, corresponding to multiple action evolution (i. e. the evolution of a set of features) of platforms, in contrast to single action evolution in [GE12]. Finally, the conclusion in Section 5 includes a summary of the paper. 2 Case Study: Communication Platforms and Scenarios In this section we introduce our main case study Apache Wave which is a communication plat- form that was originally developed by the company Google as Google Wave. Google itself has stopped the development of Google Wave, but the development is continued by the Apache Soft- ware Foundation as Apache Wave[Apa12]. One of the most interesting aspects of Apache Wave is the possibility to make changes on previous contributions. Therefore, in contrast to email, text chat or forums, due to possible changes the resulting data of the communication does not necessarily give a comprehensive overview on all interactions of the communication. For this reason, in Apache Wave for every communication there is a history allowing the users to replay interactions of the communication step by step. So for the modelling of Apache Wave it is necessary that we do not only model the systems and the communication but also the history of the communication. We have chosen Apache Wave as running example for this paper because it includes typical modern features of many other communication systems, such as near-real-time communication. This means that different users can simultaneously edit the same document, and changes of one user can be seen almost immediately by the other users. Note that we do not focus on the communication between servers and clients in this contribution but on the communication between users. In Apache Wave users can communicate and collaborate via so-called waves. A wave is like a document which can contain diverse types of data that can be edited by different invited users. The changes that are made to a wave can be simultaneously recognized by the other participating users. In order to keep track of the changes that have been made, every wave contains also a history of all the actions in that wave. Apache Wave supports different types of extensions which are divided into gadgets and robots. The extensions are programs that can be used inside of a wave. The difference between gadgets and robots is that gadgets are not able to interact with their environment while robots can be seen as automated users that can independently create, read or change waves, invite users or other robots, and so on. This allows robots for example to do real-time translation or highlighting of texts that are written by different users of a wave. Clearly, it is intended to use different robots for different tasks and it is desired that multiple robots interact without conflicts. This makes the modelling and analysis of Apache Wave very important in order to predict possible conflicts or other undesired behaviour of robots. In [EG11] we have already shown that Google Wave (and thus also Apache Wave) can be ade- quately modelled using algebraic high-level (AHL) nets, which is an integration of the modelling technique of low-level Petri nets [Roz87, Rei85] and algebraic data types [EM85]. Figure 1a shows a small example of the structure of an AHL-net Platform which has three Proc. PNGT 2012 2 / 12 ECEASST w : wavelet u : user new wavelet n = new(user,free) next = next(free) id : nat invite user invited(o, user1) = true n = addUser(o,user2) user user user user user1 7 user2 user1 7 user2 n n o o n free next Platform insert txt: text, pos: nat invited(o,user) = true n = insText(o,txt,pos) remove rng: range invited(o, user) = true n = remText(o, rng) user user o n (a) AHL-net Platform for an Apache Wave platform w : wavelet u : user new wavelet n = new(user,free) next = next(free) modify copy txt: text, rng: range invited(o,user) = true r = remText(o,rng) n = insText(r,txt,start(rng)) id : nat invite user invited(o, user1) = true n = addUser(o,user2) user user user user user1 7 user2 user1 7 user2 n o 7 n o o n free next Platform' (b) Modified AHL-net Platform′ Figure 1: Apache Wave platforms places and four transitions with firing conditions, where the pre and post arcs are labelled with variables of an algebraic signature. The AHL-net Platform models an Apache Wave platform with some basic features like the creation of new waves, modifications to existing waves, and the invitation of users to a wave which are modeled by the transitions new wavelet, insert, remove and invite user. A wavelet is a part of a wave that contains a user ID, a list of XML documents and a set of users which are invited to modify the wavelet. For simplicity we model in our example only the simple case that every wavelet contains only one single document and the documents contain only plain text. In order to obtain a more realistic model one has to extend the used algebraic data part of the model. remove1 : remove invite1 : invite user new1 : new wavelet insert1 : insert u1 : u id1 : id user free next u2 : u w1 : w n user user o u3 : u w2 : w user n u4 : u user2 user1 o u6 : uu5 : u w3 : w user2 user1 n user o w4 : w n user new2 : new wavelet free id3 : id next u8 : u user user insert2 : insert user u9 : uw5 : w n o user w6 : w n id2 : id u7 : u Wave Figure 2: AHL-process Wave of a wave As we have shown in [EG11] a suitable modelling technique for waves together with their histories are AHL-processes with instantiations. Figure 2 shows an example of an AHL-process Wave which abstractly models a wave that contains two wavelets created by possibly different users. Another interesting aspect of the modelling of Apache Wave are dynamic changes to the structure of the platform. Using rule-based transformation of AHL-nets [PER95] in the sense of graph transformation [Roz97], we can delete and add features, leading to a new platform. Figure 1b shows a net Platform′ which is an adaptation of our example Platform where the insert and remove transitions have been replaced by a modify copy transition which enables the user to replace text in a new copy of a wavelet while the original wavelet remains unchanged. 3 / 12 Volume 51 (2012) Process Evolution based on Transformation of Algebraic High-Level Nets In order to model also the dynamic modification of scenario nets we need also rule-based mod- ification of AHL-process nets. Since it is possible that the communication platform is modified at runtime there may already exist some waves that correspond to the old version of the platform. In some cases that correspondence could be violated by the modification of the platform. modify2 : modify copy invite1 : invite user new1 : new wavelet modify1 : modify copy u1 : u id1 : id user free next u2 : u w1 : w n user user o u3 : u w2 : w user n u4 : u user2 user1 o u6 : uu5 : u w3 : w user2 user1 n user o w4 : w n user new2 : new wavelet free id3 : id next u8 : u user user modify3 : modify copy user u9 : uw5 : w n o user w6 : w n id2 : id u7 : u Wave' w7 : w o w8 : w o w9 : w o Figure 3: Modified AHL-process Wave′ An intuitive solution is to apply the modification of the platform also to the wave, replacing all occurrences of the old features with corresponding new ones if possible, or remove them otherwise. For this purpose, the rule which is used for modification of the platform should be equipped with additional information, describing how the changes of the platform affect occur- rences of platform actions in a scenario. In the case of our example Wave and the platform evolution described above this leads to a new wave model Wave′ depicted in Figure 3. The two occurrences of insert as well as the occurrence of remove have been replaced by occurrences of the transition modify copy and there are new wavelet places in the post domain of the new tran- sitions, representing the unchanged originals. In our theorem in Section 4 we present a general construction to obtain under certain conditions a suitable modification of scenarios based on the evolution of the corresponding platform. 3 Modelling of Communication Platforms and Scenarios Using Al- gebraic High-Level Nets and Processes In the following we review the definition of AHL-nets and their processes from [Ehr05, EHP+02] based on low-level nets in the sense of [MM90], where X⊕ is the free commutative monoid over the set X . Note that s ∈ X⊕ is a formal sum s = ∑ni=1 λixi with λi ∈ N and xi ∈ X meaning that we have λi copies of xi in s and for s′ = ∑ n i=1 λ ′ i xi we have s⊕s ′ = ∑ n i=1 (λi + λ ′ i )xi. An algebraic high-level (AHL-) net AN = (Σ,P,T, pre, post,cond,type,A) consists of a sig- nature Σ = (S,OP; X) with additional variables X ; a set of places P and a set of transitions T ; pre- and post domain functions pre, post : T → (TΣ(X)⊗ P)⊕; firing conditions cond : T → P f in(Eqns(Σ; X)); a type of places type : P → S and a Σ-algebra A. The signature Σ = (S,OP) consists of sorts S and operation symbols OP, TΣ(X) is the set of terms with variables over X , the restricted product ⊗ is defined by (TΣ(X)⊗P) ={(term, p)|term ∈ TΣ(X)type(p), p ∈ P} Proc. PNGT 2012 4 / 12 ECEASST and Eqns(Σ; X) are all equations over the signature Σ with variables X . An AHL-net morphism f : AN1 → AN2 is given by f = ( fΣ, fP, fT , fA) with signature morphism fΣ, functions fP and fT , and generalized algebra homomorphism fA satisfying the following conditions: (1) ( f # Σ ⊗ fP)⊕◦ pre1 = pre2 ◦ fT and ( f #Σ ⊗ fP) ⊕◦ post1 = post2 ◦ fT , (2) cond2 ◦ fT = P f in( f #Σ)◦cond1, and (3) type2 ◦ fP = fΣ ◦type1. The category defined by AHL-nets and AHL-net morphisms is denoted by AHLNets where the composition of AHL-net morphisms is defined componentwise. An example of an Apache Wave platform is given by the AHL-net Platform in Figure 1a (for more details, signature and algebra see [Gab12]). The firing behaviour of AHL-nets is defined analogously to the firing behaviour of low-level nets. The difference is that in the high-level case all tokens are equipped with data values. More- over, for the activation of a transition t, we additionally need an assignment v of the variables in the environment of the transition, such that the assigned pre domain is part of the given marking and the firing conditions of the transition are satisfied. This assignment is then used to compute the follower marking, obtained by firing of transition t with assignment v. For an example of the firing behaviour we refer to our technical report [Gab12]. Now, we introduce AHL-process nets based on low-level occurrence nets (see [GR83]) and AHL-processes according to [Ehr05, EHP+02]. The net structure of a high-level occurrence net has similar properties like a low-level occurrence net, but it captures a set of different concurrent computations due to different initial markings. Moreover, in a low-level occurrence net with an initial marking there is for any complete order of transitions compatible with the causal relation a corresponding firing sequence once there is a token on all input places. This is a consequence of the fact that in an occurrence net the causal relation is finitary. In the case of high-level occurrence nets an initial marking additionally contains data values and in general some of the firing conditions in a complete order of transitions are not satisfied. Hence, even in the case that the causal relation is finitary, we cannot expect to have complete firing sequences. In order to ensure a complete firing sequence in a high-level occurrence net there has to be an “instantiation” of the occurrence net (see [Ehr05]). Instantiations, however, are not considered explicitly in this paper, and we refer to our technical report [Gab12] where all constructions and results for AHL- process nets are also shown for their instantiations. In the following definition of AHL-process nets, in contrast to occurrence nets, we omit the requirement that the causal relation has to be finitary, because this is not a meaningful requirement for our application domain. Definition 1 (Algebraic High-Level Process Nets and Processes) An AHL-process net K is an AHL -net K = (Σ,P,T, pre, post,cond,type,A) such that for all t ∈T with pre(t) = ∑ni=1(termi, pi) and notation •t ={p1,..., pn} and similarly t• we have 1. (Unarity): For all p ∈ P there exist no terms term1,term2 ∈ TΣ(X)type(p) such that (term1, p)⊕(term2, p)≤ pre(t) or (term1, p)⊕(term2, p)≤ post(t), 2. (No Conflicts): •t ∩•t′ = /0 and t •∩t′•= /0 for all t,t′ ∈ T,t 6= t′, and 3. (Partial Order): the causal relation