Petri nets are a formalism for describing systems where interactions between active components { so-called transitions { are modeled as exchanges of tokens over passive places. Whether a transition may re is solely dependent on the availability of tokens in its incoming places; similarly a transition forwards control to subsequent transitions by storing tokens in their respective input places. This interaction model of strong decoupling through local actions and local e ects makes distributed systems modeled via Petri nets highly extensible. In this paper, we present the syntax and semantics of a model that leverages the extensibility provided by Petri nets for representing BPEL processes in a way that enables their distributed and decentralized execution using tuplespace middleware. Said middleware implements the proposed Petri net dialect and therefore allows for direct, distributed execution of the modeled processes.
Petri nets were originally designed as a model for arbitrary extensible computer
architectures i.e. machines that consist of many individual modules, each of them
responsible for a particular task of the overall system. Adding a new module has
no impact on the existing ones, their performance characteristics for instance do
not change at all. Three underlying design principles [
These principles build the foundation for our model, that is naturally based
on Petri nets. In their spirit, we de ne a set of individual components and the
communication between them. The communication middleware that facilitates
component interaction during execution of the model is based on tuplespaces,
since (i) they closely resemble the design properties of petri nets in terms of loose
coupling and asynchronous communication [
Tuplespace technology has its origin in the Linda coordination language,
de ned in [
In this paper, we de ne a variant of Petri nets, called Executable Work ow
Networks (EWFN), speci cally designed to represent BPEL work ows and being
executed \natively" on an extended, Linda-like tuplespace system. The basis
for our model are colored, non-hierarchical Petri nets (CPN) [
De nition 1 (EWFN). An EWFN is a directed, bipartite graph
EWFN = ( ; P; T; F; X; A; M0; Lw)
= fCF; DATA N; DATA N String; : : : ; g denotes the set of tokens
(tuples). Note that comprises two di erent categories of tokens: (i) control
ow tokens CF = (\CF" S N N N) with S = f\POS"; \NEG"; \FAIL"g
denoting either \positive", negative (a.k.a dead path, a special form of \negative"
control ow necessary for dead path elimination in WS-BPEL) or control ow
initiated by a failure, and (ii) data tokens representing BPEL variables and
process meta-data. The three integer elds represent processID, instanceID and
scopeID in order to be able to distinguish between process models, process
instances and scopes that were initiated by event-handlers. Data tokens consist of
the generic data tuple (denoted as DATA = (\DATA" N N)) concatenated
with variable de nitions (in tuple form) from the respective process. We represent
arbitrary structured data by serializing its tree-based representation (e.g. in
the form of an XML-DOM [
Note that like most other formalizations of Petri nets, our description is based on multi-sets, we therefore de ne the operators +, , etc. to be de ned on multi-sets as well.
P is a nite set of places and T a nite set of transitions such that P \ T = ;.
F (T P ) [ (P T R), with R = fread; takeg is a set of arcs known as
ow relation. The set F is subject to the constraint that no arc may connect two
places or two transitions. The arc types correspond to classical Linda operations
[
X is a set of templates in tuple form, that may either contain a wildcard (?) or a concrete value as element.
A : (P T R) ! X is a function that assigns templates to incoming arcs of a transition such that 8(p; t; r) 2 F \ (P T R) : A((p; t; r)) 2 X. Sometimes, we use A without the last parameter, as a shortcut to access the template assigned to an arc pointing to a transition. In these cases, it is not important whether the template is used in a read or a take operation.
M0 : P ! MS is an initialization function that assigns a multi-set over to places such that 8p 2 P : M0(p) 2 MS This function initializes the network by assigning a multi-set of colored tokens to each place. It is also allowed that the expression is missing, i.e. a place is initialized with the empty color multi-set.
Lw : (T P ) ! is the Linda write function that determines the token to be written by each outgoing arc of a transition. Writing an empty tuple ( ) means that no tuple is written at all.
De nition 2 (tuple element). A tuple element T E is a tuple (p; tu), p 2 P ,
tu 2
De nition 3 (marking). A marking M 2 T EMS is a multi-set (denoted as
MS ) over tuple elements. Each place may contain one or more equal tuple elements,
thus the marking is de ned as a multi-set. Note that we may also use M as a
function such that 8p 2 P : M (p) 2 MS
De nition 4 (Lr). Linda read operations (destructive and non-destructive) are
formalized as a function Lr : X MS ! . According to Linda's semantics
[
is a binary relation over the sets a tuple: X.
and X, specifying if a template matches (tu; te) 2 i jtuj = jtej ^ (8n 2 1:: jtej : n(te) = n(tu) _ n(te) = ?) i(t) returns a projection to the ith component of a tuple tu, jtuj denotes the size of a tuples, i.e. the number of elements it contains.
A template therefore is a tuple that has either a wildcard (denoted by the ? character) or a concrete value on each position. A template matches a tuple i (i) both have the same number of elements and (ii) each concrete value in the tuple equals the value on the same position in the template, or (iii) the template has a wildcard on this position.
De nition 5 (strongly connected). An EWFN is called strongly connected
[
Similar to WF-nets [
A transition t 2 T that executes a destructive read operation (a.k.a take) changes marking M1 to M2 as follows: 8p 2 t : M2(p) = M1(p)
Lr(A((p; t; \take")); M1(p))
A transition t 2 T that executes a non-destructive read operation in contrast, does not have any e ect on the marking:
8p 2 t : M2(p) = M1(p)
The set of places that have arcs pointing to transition t is denoted as t = fpjpF tg, the set of transitions that have arcs pointing to place p is denoted as p = ftjtF pg, with F being the ow relation. t and p are de ned accordingly. De nition 6 (enabled). A transition t 2 T is called enabled in marking M i 8p 2 t : Lr(A((p; t)); M (p)) 6= ;
It is important to notice that the templates of read operations may overlap,
i.e. if two di erent transitions destructively read from the same place with
templates that (partially) match the same tuple, a con ict is created. According
to Linda semantics [
De nition 7 (con ict-free enabled). A transition t 2 T is called con ict-free enabled in marking M i t is enabled ^ 8t0 2 ( t) n ftg : t0 is not enabled _ 8p 2 t \ t0 : Lr(A((p; t)); M (p)) 6= Lr(A((p; t0)); M (p)) _ (8p 2 t \ t0 : Lr(A((p; t)); M (p)) = Lr(A((p; t0)); M (p)) ^
(p; t; \read") 2 F ^ (p; t0; \read") 2 F )
Intuitively, a transition t is con ict free enabled if all other transitions t0
that share an input place with this transition are not enabled, they do not read
the same tuple or they read the same tuple but all issue non-destructive read
operations only on the place in question. Since we describe executable work ows,
con ict situations where the actual decision is not-determined and ultimately
lead to \confusion" [
The property of con ict-freeness however is de ned on enablement of a transition, i.e. it can only be checked during runtime. The following, alternative de nition de nes con ict-freeness of a transition based on the templates of the read operations it issues, thus allows to check for con ict-freeness of an EWFN on the syntactical level, i.e. check an EWFN after transformation from BPEL. De nition 8 (con ict-free transition). A transition t 2 T is called con ictfree i 8p 2 t 8t0 2 p n ftg : A((p; t)) \ A((p; t0)) = ; _
((p; t; \read") 2 F ^ (p; t0; \read") 2 F )
A transition t is con ict-free i the intersection of templates of the read operations from di erent transitions reading from shared places with t is empty, or every transition in question issues only non-destructive read operations. For the reasons mentioned before, we enforce all transitions in an EWFN to be con ict free.
De nition 9 (satis ed). A template te 2 X is called satis ed on multi-set tuMS i Lr(te; tuMS ) 6= ;. This can also be written as function Sat : X MS ! B.
Sat(te; tuMS ) =
true; if Lr(te; tuMS ) 6= ; false; otherwise De nition 10 ( re). A transition t 2 T that is enabled in marking M1 may re and change marking M1 to M2 as follows: 8p 2 t [ t : M2(p) = M1(p)
X Lr(A((pn; t)); M1(pn)) +
X Lw(t; pn) Note that in this de nition, the operators +, and P are de ned on multi-sets, removing and adding tuples from the multi-set respectively.
We extend the template matching from De nition 4 to be able to understand join variables as elds in a template tuple. Join variables allow to express a restriction on the enablement of a transition such that it is only enabled if every template of its read/take operations that use a join variable is satis ed and the tuple elements on the position of the join variable are equal for each join variable. Note that for the matching itself a join variable is treated as wildcard (?).
Consider the join of two threads of control ow of the same work ow instance and process model, identi ed by the ids iid and pid respectively: te1 = (\CF"; ?pid; ?iid) te2 = (\CF"; ?pid; ?iid) The transition using two separate take operations with te1 and te2 as templates is only enabled if there are tuples available in both incoming places that have equal values on their second and third position.
De nition 11 (join matching). A transition t 2 T that uses join variables in its template operations is enabled in marking M i 8p 2 t : Lr(A((p; t))[? =?]; M (p)) 6= ; ^ 8p1; p2 2 t 9n 2 N : n(A((p1; t))) is join variable ^ n(A((p2; t))) is join variable ^ n(A((p1; t))) = n(A((p2; t))) ^ n(Lr(A((p1; t)); M (p1))) = n(Lr(A((p2; t)); M (p2)))
The treatment of join variables for the actual matching is expressed as [? =?], meaning that every variable that starts with a ? is replaced by a wildcard (?).
For space reasons, we omit the usual de nitions for ring sequence, reachability,
liveness, boundedness, safeness well structuredness and well-formedness [
In this paper, we presented a tuplespace-based Petri net dialect that is natively executable on a tuplespace system, i.e. each element of the Petri net has an equivalent element or operation on a tuplespace. An EWFN therefore is a kind of \byte code" for tuplespace-based applications; they can be designed using EWFNs and then directly transformed to a running application.
The main idea behind the development of EWFNs however is their use in decentralized work ow enactment. We are working on a BPEL engine that transforms BPEL les to EWFNs and then executes them based on tuplespaces. Each tuplespace can reside on a di erent machine in the network, thus the engine and even the execution of a single process instance may be arbitrarily distributed. The key enabler for this architecture are Petri nets and their inherent properties such as: no central point of control, local actions, local e ects, asynchronous interaction.