Transcript Petri net

Lecture 5
Process management
Technology of information systems
Contents
•
•
•
•
Introduction
Petri net summary
Workflow nets and soundness
A sound SOA framework
Technology of information systems
Introduction
• Coordination is needed at several levels:
– For business processes: this is called workflow
management and it is performed by workflow engines
– In (service) components: this called orchestration and
is performed by worklow-like engines (e.g. BPEL)
– Between components: it is called choreography and is
perfomed by middleware, such as an enterprise bus
• In all cases coordination means the execution of
a process.
• Coordination components are configured by
process models.
Technology of information systems
Petri net (1)
Definition:
a labeled transition system is 4-tuple:
•
•
•
•
TS = <S,A,R,s> such that
S set of states
A set of actions or events
R  SxAxS the transition relation
s  S is the initial state
Reachability:
• s a s’ iff (s,a,s’) R
• s * s’ iff s = s’   a  A, s”  S: s a s”  s” * s’
Technology of information systems
Petri net (2)
Definition Petri net:
• a Petri net N is 3-tuple: N=<P,T,F>
– P set of places
– T set of transitions
– F: (PxT)  (TxP)  IN the flow relation
• a marking M is a bag over P (element of bag.P)
• (N,M) denotes a Petri net N with (initial) marking M
• subnet N’ of N: all elements of N’ are subsets of the
elements of N
3
2
t
4
Technology of information systems
Petri net (3)
Notations:
1. t is the preset of transition t,
similarly: t is the postset of t
2. t, t  bag.P, bags over the places
3. t(p) = F(p,t) and t(p) = F(t,p)
4. the flow matrix: [N]
[N](p,t) = F(t,p) - F(p,t)
5. A bag over {a,b,c,d} with 3 a’s, 2 b’s and 1 c is
denoted by [a3,b2,c]
Extra: inhibitor arcs:
◦t: P  {true, false}, ◦t(p)=true iff p is an inhibitor for t
Technology of information systems
Petri net (4)
Transition system of a Petri net
• Petri net: <P,T,F>
• Petri system (<P,T,F>,M)
M is initial marking
• Transition systems: <S,A,R,s>
• S = bag.P
• A=T
• R = {(m,t,m’) | m ≥ t  m’ = m - t + t }
• s=M
In case of inhibitor arcs:
• R={(m,t,m’) | m ≥ t  m’ = m - t + t 
 p  P: ◦t(p) = true  m(p) = 0}
Technology of information systems
Petri net (5)
• Petri nets may have an infinite state space.
• Petri nets with inhibitor arcs are Turing complete.
t1
t3
t2
t4
Technology of information systems
Petri net (6)
Two safe and fair traffic lights
red1
red2
safe2
yr1
yr2
rg1
rg2
yellow1
yellow2
gy1
gy2
safe1
green1
Technology of information systems
green2
Petri net (7)
Semantics
x
y
• interleaving: x or y
• step: x or y or (x and y)
• multi-step:
x or y or (x and y) or 2.x or
2.y
we use interleaving semantics
Technology of information systems
Petri net (8)
Notions:
• Firing sequence <t1,..., tn> for M if
from marking M the transitions can
successively fire
• Parikh vector of a firing sequence 
is a vector :TIN that is the bag of
 , i.e.: if  = <a,b,c,a,d,e,c,b,c>
then  = [a2,b2,c3,d,e]
Technology of information systems
Petri net (9)
Two essential properties:
• marking equation
if M  M’ then M’ = M + [N].
• additivity of markings
if Mi i Mi’ then for all interleavings  of
1 .... n: M1 + ... + Mn M1’+...+Mn’
Technology of information systems
Petri net (10)
More notions:
• reachability: M’ is reachable from M iff
M * M’
• reachability graph: graph with markings as nodes and
transitions as arcs (M,t,M’) iff M t M’
• liveness: transition t is live if for all markings M there is a
reachable marking M’ with •t ≤ M’
• dead: transition t is dead in M iff t is not enabled in any
reachable marking M’ from M
• deadlock: marking M is a deadlock iff no transition in M is
enabled
Technology of information systems
Petri net (11)
More notions:
• k-Boundedness: in all reachable markings the
number of tokens  k
• safety: 1-boundedness
• Conservative net: (N,M) iff all reachable markings
have the same number of tokens
• Home marking
a marking M’ is a home marking of (N,M)
iff for all reachable M” we have M” * M’
Technology of information systems
Workflow net (1)
Definition of workflow net:
A Petri net N is a WF-net iff
• N has two special places: i and f
• Every node is on a directed path
from i to f
t
Equivalent definition:
the closure is strongly
connected
Technology of information systems
i
(the remainder of N)
f
Workflow net (2)
WF-nets are used to model:
• Work processes where cases or jobs have to be
executed
• Example of cases or jobs are:
– A claim in an insurance company
– The assembly of a bike
– A complex update in a database (all amounts have to be
transformed from dollars into euro’s)
– Handling of a request in a SOA component
• Each transition represents a task to be performed by
a resource
Technology of information systems
Workflow net (3)
Example
check_policy
NOK
c4 send_letter
2x!
OK
c1
start
c5
register
NOK
c2
check_damage
OK
Technology of information systems
c3
pay_damage
Workflow net (4)
check_policy
NOK
c4 send_letter
OK
c1
start
c5
register
c2
check_damage
NOK
OK
Technology of information systems
c3
pay_damage
Workflow net (5)
Definition of soundness
a WF-net is k-sound iff [fk] is a home marking for
initial marking [ik], i.e.
M: ( [ik] * M )  ( M * [fk] )
A WF-net is sound iff it is k-sound for all k.
Soundness is a very important property: it means that
workflows are able to end in a proper way
Technology of information systems
Workflow net (6)
Examples
f
i
1-sound, not 2-sound
i
k
k
f
exactly n x k-sound
Technology of information systems
Workflow net (7)
Properties
1. If sound then M: ([ik] * MM  [fk])M = [fk]
2. If the closure is live and bounded then a WF- net is
1-sound
3. If a WF-net is 1-sound, then its closure is bounded.
4. k-soundness is decidable
5. Soundness is decidable
Technology of information systems
Workflow net (8)
Special structured WF-nets:
A Petri net is a State Machine WF-net (SMWF) iff it
is a WF-net and
 t T: |t| = 1  |t| = 1
Properties
•For every SMWF N, (N,[i]) is conservative
•Every SMWF N is a sound WF-net
Technology of information systems
Workflow net (9)
A Petri net is a Marked Graph WF-net (MGWF) iff it
is a WF-net and
 p  P : |p| ≤ 1  |p| ≤ 1
Properties:
• (N,[i]) is safe and every loop-free path from i to f
has at most one token
• (N,[ik]) is k-bounded
• Every acyclic MGWF is sound
Technology of information systems
Workflow net (10)
A Petri net is a Free Choice WF-net (FCWF) iff it
is a WF-net and
 t1,t2  T : t1  t2    t1 = t2
Properties:
• Every SMWF-net and every MGWF-net is a FCWFnet
• A 1-sound FCWF-net is sound
Technology of information systems
Workflow net (11)
Construction techniques
idea:
• Correctness by construction
• If we have sound nets and we compose them to
bigger ones in the right way, we want sound nets
again
• Also correctness by reduction: find patterns and
reduce a net to a sound one, and expand again to
the original one by “legal” constructions
Technology of information systems
Workflow net (12)
Rule 1: place refinement
Rule 2: transition refinement
Rule 3: place duplication
Rule 4: transition duplication
Rule 5: iteration
Property:
Start with one place and apply the rules:
the net is always a sound WF-net.
Restriction: rule 5 may not be applied to i or f.
Technology of information systems
Sound SOA framework (1)
Sell side of a component
Component
request
no offer
deciding
Choreography/Sell
Orchestration
offer
reject
accept
waiting
failure
success
processing
finishing
idle
start
Technology of information systems
payment
failure
success
Sound SOA framework (2)
General task structure
request
no offer
offer
reject
accept
failure
success
failure
success
payment
Choreography/Sell
Orchestration
start
Component
Task/Buy
started
requested
request
offered
no offer
offer
accepted
reject
accept
Technology of information systems
completed
failure
success
payment
Sound SOA framework (3)
Overview
request
no offer
offer
reject
accept
failure
success
payment
Component
Choreography/Sell
Orchestration
Orchestration
Task/Buy
Orchestration
Task
Task
Task/Buy
Each task is realized internally or by an external service
Technology of information systems
Sound SOA framework (4)
Orchestration: Sequential composition
(Compound) Task
(Compound) Task
Sequence
Technology of information systems
Sound SOA framework (5)
Orchestration: Choice construct
(Compound) Task
(Compound) Task
Choice
Technology of information systems
Sound SOA framework (6)
Orchestration: Parallel composition
n
failures
(Compound) Task
n
successes
(Compound) Task
Parallel
Technology of information systems
Sound SOA framework (7)
Orchestration: While construct
F
T
(Compound) Task
While
Technology of information systems
Sound SOA framework (8)
Soundness argument
i
o
Orchestration
Verification
Technology of information systems
Sound SOA framework (9)
The price of a service in this framework
Assumptions:
• For each service the lowest price is k with
probability pk
• We are prepared to pay at most m
So:
• The expected cost of a task is: c= ∑k=1->m k. pk
• The probability of success: s= ∑k=1->m pk
• The probability of failure: 1-s
Technology of information systems
Sound SOA framework (10)
The price of a compound task to be
computed in a recursive way
Sequential composition: (tasks a and b)
C(a) is the expected cost of task a
Technology of information systems
Sound SOA framework (11)
Parallel composition:
Technology of information systems
Sound SOA framework (12)
Choice construct:
Technology of information systems
Sound SOA framework (13)
α
While construct:
a
1-α
All these operators are associative!
Technology of information systems