Information Technology Reference
In-Depth Information
Figure 2.2a is not sound because starting from
i
,either
t
1
or
t
2
can fire
and therefore either
p
2
or
p
3
contains a token. Then
t
3
is never enabled
because it needs tokens in both
p
2
and
p
3
, and therefore state
o
is not
reachable. This is called a
deadlock
when no transition can fire after
either
t
1
or
t
2
fires. A sound implementation is shown in Figure 2.2c
where the firing of either
t
1
or
t
2
can enable
t
3
and the deadlock is
eliminated.
Requirement 2 says when a workflow reaches a final state
o
, all
other places should not contain any token. Figure 2.2b illustrates a
workflow net that does not fulfill this requirement. Let us think about a
modified version of the travel request approval process in which a
request needs to be approved by both line manager (activity
t
2
) and
comptroller (activity
t
3
), and then archived for later reference
(activity
t
4
). The WF-net in Figure 2.2b is not sound because starting
from
i
, after
t
1
(an activity to split a task and send to two subsequent
tasks) fires, both
t
2
and
t
3
are enabled since each of
p
2
and
p
3
contains a
token. Later
t
2
can fire and
p
4
contains a token, which in turn enables
t
4
.
When
t
4
fires,
p
5
(i.e., place
o
) contains a token. However, in the
meanwhile
p
3
still contains a token, which violates requirement 2. This
is called
lack-of-synchronization
where two or more activities should
be synchronized but actually not. A sound implementation is shown in
Figure 2.2d where
t
4
is enabled only after both
t
2
and
t
3
fire.
2.3 COLORED PETRI NETS
As we mentioned earlier, places usually represent messages or
resources in workflows. Therefore, by introducing types to tokens,
one can distinguish messages or resources in a workflow. In basic Petri
nets the tokens in different places are indistinguishable. The formal-
ism of colored Petri nets, as an extension to the basic Petri nets, was
stimulated by the idea that each token should have a
type
assigned
to it.
Before we define colored Petri nets, we first need to define
multiset
,
which is the extension of the set concept.
N
denotes the set of all
nonnegative integers.
Definition 2.5. (Multiset)
A multiset
m
, over a nonempty set
S
,isa
N
that we represent as a formal sum,
P
s2S
m
0
s
function
m
:
S
!
ð
s
Þ
