交互式陪替氏网：并发系统建模与兼容性分析
88 浏览量
更新于2024-08-26
收藏 755KB PDF 举报
"交互式陪替氏网是用于建模并发系统如Web服务和工作流系统的 Petri 网模型。这种模型分析了系统行为，发现潜在问题，并优化设计。文章定义了兼容性和弱兼容性概念，揭示了它们与活性、可逆性和有界性之间的关系，并证明了（弱）兼容性问题是 NP-难的。此外，还提出了 IPN 的分类体系，以探索某些子类的特性。"
交互式陪替氏网（Interactive Petri Nets, IPNs）是一种特定类型的 Petri 网，特别适用于建模那些由多个子系统通过消息通道相互作用的并发系统。这些子系统通过通信来协同执行任务，而 IPNs 正是用来描述和分析这种交互行为的工具。通过 IPNs，可以深入理解系统的动态行为，识别可能存在的问题，从而对系统设计进行改进。
在并发系统中，兼容性是一个关键概念，它反映了系统各子系统之间正确或适当交互的可能性。文章中进一步定义了弱兼容性，旨在更细致地刻画实际应用中的不同合作能力。作者探讨了（弱）兼容性与活性、可逆性和有界性等重要性质之间的关联，这些性质对于理解系统的稳定性和可控性至关重要。
活性（liveness）是指系统能否持续进行有意义的操作，不陷入死锁或停滞状态；可逆性（reversibility）则关注系统是否能够在执行操作后恢复到先前状态；有界性（boundedness）是指系统资源的使用是否有限制，避免无限增长导致的问题。通过这些性质的分析，可以评估系统的性能和可靠性。
文章还证明了在 IPNs 中判断（弱）兼容性是一个复杂度为 co-NP 难的问题，这意味着在最坏情况下，解决这个问题的难度随着问题规模的增加呈指数级增长。这为实际应用中的算法设计和复杂性分析提供了理论基础。
最后，为了深入研究 IPN 的特性和子类，文章提出了一种分类方法。这种分类有助于识别和研究 IPN 的特定子类，可能有助于开发更高效、针对性更强的分析技术和设计策略，以适应不同的并发系统需求。
"交互式陪替氏网"的研究论文为并发系统的建模和分析提供了一个新的视角，通过引入兼容性和弱兼容性概念，以及探讨其与系统性质的关系，为理解和优化这类系统提供了有价值的理论工具和方法。
LIU et al.: INTERACTIVE PETRI NETS 293
{M
0
}, which still fulfills the definition of reversibility. How-
ever, we do not consider this special case in this paper since
this kind of net, which is dead at the initial marking, is not
meaningful. In other words, we always assume that there is at
least a transition enabled at the initial marking.
A nonempty subset of places S (respectively Q)iscalleda
siphon (respectively trap)if
•
S ⊆ S
•
(respectively
•
Q ⊇ Q
•
).
A siphon is minimal if it does not contain any other siphon.
A net N =(P, T, F) is called as:
1) an ACN if ∀p
1
, p
2
∈ P : p
•
1
∩ p
•
2
= ∅ ⇒ p
•
1
⊆ p
•
2
∨
p
•
2
⊆ p
•
1
;
2) an FCN if ∀p
1
, p
2
∈ P : p
1
= p
2
∧ p
•
1
∩ p
•
2
= ∅ ⇒
|p
•
1
| = |p
•
2
| =1;
3) a marked graph (MG) if ∀p ∈ P : |p
•
| = |
•
p| =1;
4) a state machine (SM) if ∀t ∈ T : |t
•
| = |
•
t| =1.
III. IPN
AND COMPATIBILITY
This section defines IPNs, presents their compatibility, and
reveals the complexity to analyze it.
A. IPN
First, a logic process is defined to model the state transition
of a subsystem.
Definition 1: A logic process (LP) is a net N =(P, T, F )
that satisfies the following two points.
1) N has two special places α and β, where α ∈ P is
called source place, β ∈ P is called sink place, and
•
α = β
•
= ∅.
2) Let N
E
=(P, T ∪{b},F ∪{(b, α), (β, b)}) be the triv-
ial extension of N and M
0
= α be its initial marking.
Then, N
E
is strongly connected, and (N
E
,M
0
) is live
and safe.
If places c
1
−c
16
in Fig. 2 are deleted, then the resulting nets
are three LPs. An LP starts from a “source” place α and ends
at a “sink” place β. Safety of (N
E
,M
0
) means that it has a
finite number of states and each place can have at most one
token. Safety and liveness imply that it can return to its initial
state after its completion. Transition b in N
E
is called a bridge
transition.
Property 1: Let N =(P, T, F) be an LP and M
0
= α be its
initial marking. Then, (N
E
,M
0
) is reversible.
Proof: Let M ∈ R(N
E
,M
0
). Because (N
E
,M
0
) is live
and safe, we can easily draw the following conclusion:
1) M (α)=0if and only if M (P \{α}) > 0, and 2) M(α)=
1 if and only if M (P \{α})=0. That is, α and P \{α}
cannot be marked at the same time. Because (N
E
,M) is also
live, bridge transition b is live at M . Hence, after firing b
in (N
E
,M), there is M
∈ R(N
E
,M) such that M
(α)=1.
Hence, M
(P \{α})=0, i.e., M
= M
0
. Hence, (N
E
,M
0
) is
reversible.
Note that, it is known by Property 1 that, when the sink place
β has a token in (N
E
,M
0
), other places have no tokens. In
fact, an LP is a sound workflow net, and the aforementioned
conclusion is easily derived by the soundness of workflow nets
[3]. A subsystem needs message channels to communicate with
other subsystems. Hence, the following definition is given.
Fig. 2. Three LPCs.
Definition 2: A logic process with channels (LPC) is a net
N =(P
A
∪ P
I
∪ P
O
,T,F) such that the following holds.
1) The subnet generated by P
A
= ∅ is an LP, where P
A
is a
set of action places of N.
2) P
I
is a set of input channel places, P
O
is a set of output
channel places, P
I
∩P
O
=∅, and P
A
∩(P
I
∪P
O
)=∅.
Fig. 2 shows three LPCs in which α
1
−α
3
are source places,
β
1
−β
3
are sink places, and c
1
−c
16
are channel places. A set of
LPCs can make up an IPN.
Definition 3: IPNs are defined recursively as follows.
1) An LPC N =(P
A
∪ P
C
∪ P
I
∪ P
O
,T,F) is an IPN
where P
C
= ∅.
2) Let N
i
=(P
Ai
∪ P
Ci
∪ P
Ii
∪ P
Oi
,T
i
,F
i
), i ∈ N
2
,be
two IPNs such that (P
A1
∪ P
C1
) ∩ (P
A2
∪ P
C2
)=∅,
P
I1
∩ P
I2
= P
O1
∩ P
O2
= ∅, (P
O1
∩ P
I2
) ∪ (P
O2
∩
P
I1
)=P
S
= ∅, and T
1
∩ T
2
= ∅. Then, the
net N =(P
A
∪ P
C
∪ P
I
∪ P
O
,T,F) is an IPN
where P
A
= P
A1
∪ P
A2
, P
C
= P
C1
∪ P
C2
∪ P
S
,
P
I
=(P
I1
∪ P
I2
) \ P
S
, P
O
=(P
O1
∪ P
O2
) \ P
S
,
T = T
1
∪ T
2
, and F = F
1
∪ F
2
.
Fig. 3 shows an IPN that is composed of the three LPCs in
Fig. 2. {c
1
,c
6
,c
12
} is the set of input channel places, and {c
2
−
c
5
,c
7
− c
11
,c
13
− c
16
} is the set of internal channel places.
Clearly, an IPN N is the union of m LPCs N
1
−N
m
,
m ≥ 1, via a set of common places (i.e., P
S
). To facilitate
its description, an IPN is denoted by N = N
1
⊕ N
2
⊕···⊕
N
m
= ⊕
m
i=1
N
i
. In Definition 3, P
A
(respectively P
C
, P
I
,
P
O
, P
I
∪ P
O
)iscalledasetofaction (respectively internal
channel, input channel, output channel, and external channel)
places of N. Input channel places can only be combined with
output ones. After two LPCs are composed via a set common
channel places, these common places become internal ones and
剩余11页未读，继续阅读
156 浏览量
217 浏览量
716 浏览量
1437 浏览量
1069 浏览量
1133 浏览量
1403 浏览量
1718 浏览量
1152 浏览量
weixin_38668754
- 粉丝: 3
- 资源: 972
我的内容管理
展开
