基于Petri网的移动集群系统外生协调建模

的1的1的1理论计算机科学电子笔记154（2006）121-138www.elsevier.com/locate/entcs基于Petri网的移动集群系统外生协调建模胡安·吉伦-斯科尔滕，法哈德·阿巴布，弗兰克·德波尔，Marcello Bonsangueb，2，3aCWI，阿姆斯特丹，荷兰BLIACS，莱顿大学，荷兰摘要在本文中，我们将讨论如何建模系统，通过移动通信和协调渠道主要是，我们专注于这些渠道施加的外生协调行为建模。我们使用Petri网作为我们的建模语言，因为它们提供了一个图形和数学建模形式主义。我们给出了一组移动通道类型的Petri网这使我们能够构建应用程序的模型，通过每个组件和每个移动通道的Petri网，并将它们组合在一起。为此，我们定义了一个特殊的Petri网复合函数。我们还讨论了这些模型的分析和模拟及其外生协调行为。关键词：分布式移动通道，Petri网，协调，组合1介绍在MoCha框架[6]中，组件和流程由移动渠道协调。移动通道是一种协调原语，它允许匿名点对点通信，使系统中的通道连接能够动态重新配置，并提供外源协调。1电子邮件：{juan，farhad，frb} @ cwi.nl2 电子邮件地址：marcello@liacs.nl3Bonsangue博士的研究是由荷兰皇家艺术和科学学院的研究金促成的。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.036122J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121移动通道对于所有需要协调的实体都是有趣的，但是它们对于基于组件的软件特别有趣。正如我们在[6]中所示，它们为构建复杂的协调方案提供了一个高度表达的数据流架构，独立于组件的计算部分。MoCha框架的实现，MoCha中间件，适用于任何集中式或分散式分布式网络，我们通过移动通道外部协调组件。例如，在[7]中，我们展示了将MoCha用于P2P网络的好处本文的目的是给通过这些移动信道进行通信和协调的系统建模的方法。我们的主要目标是建模，分析和模拟这些系统的外源协调。因此，我们需要一种具有以下特点的建模语言：（1）该语言在学术界和工业界都有广泛的应用。(2)它包含了具有明确理论基础的定义良好的语义。 (3)它提供模型分析，就像所有建模语言一样。 (4)它提供模型模拟。(5)语言和它生成的模型一样容易理解。(6)最后，但并非最不重要的是，有足够的工具支持这种语言。满足上述要求的建模语言是Petri网。Petri网，以其创建者Petri的名字命名[12]，为系统的并发行为提供了一种图形和数学建模形式。它们提供了精确的语义和理论基础[15]。通过提供在Petri网模型形式中指定的移动通道这意味着，除了能够建模系统，我们自动获得以下优势：广泛的理论支持，易于使用，模型分析，模型模拟，在不同领域的即时应用，以及广泛的工具支持。此外，虽然这不是本文的主要目标，但由于Petri网模型具有清晰和精确的语义，它们也自动为我们的移动通道提供语义。感兴趣的读者可以比较[8]中给出的集中于进程交互的移动通道语义与本文中给出的集中于并发的语义。在第2节中，我们简要介绍了MoCha框架。在第3节中，我们简要介绍了Petri网。在第4节中，我们将展示如何对使用我们的移动通道的系统进行建模。本文给出了一组移动通道类型的Petri网模型，讨论了在Petri网中组件使用这些通道所需实现的最小行为，并给出了构造系统的组合函数在第5节中，我们给出了一个J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121123组件一信道写道需要水槽源组件B实例，并进行了分析和仿真。在第6节中，我们讨论了我们的方法的复杂性和对工具的需求。我们以第7节结束。2摩卡MoCha 中 的 通 道 （ 见 图 1 ） 由 一 对 两 个 不 同 的 端 点 组 成 ： 通 常 是（ source ， sink ） 用 于 大 多 数 常 见 的通 道 类 型 ， 但 也 有 （ source ，source）和（sink，sink）用于特殊类型。这些通道端可用于应用程序的组件。组件可以通过将值插入到源端来写入，并通过从通道的接收端删除值来获取;数据流是本地单向的：从组件到通道或从通道到组件。Fig. 1.一个频道的全景。通道是点对点的，它们在连接中涉及的（远程）组件之间提供定向虚拟路径。因此，使用通道来表达在应用程序内执行的通信在结构上是非常有表现力的，因为很容易看出哪些组件（潜在地）彼此交换数据。这使得在应用程序中更容易应用工具来分析依赖关系和数据流分析通道提供匿名通信。这使得组件能够与其他组件交换消息，而不必知道这些其他组件位于网络中的何处，谁产生或消费所交换的消息，以及何时产生或将消费特定消息。由于组件彼此不知道，因此很容易更新或交换其中任何一个组件，而无需了解其连接到的通道另一侧这为组合在空间和时间上解耦的组件提供了一种简单的渠道的两端是可移动的。我们在这里介绍两种移动性的定义：物理的和逻辑的。第一种定义为在分布式系统中将通道端从一个位置物理移动到另一个位置，其中位置是组件执行的逻辑地址空间。第二，逻辑移动性，通常在π演算中定义为通过通道本身将通道（-end）身份传递给应用程序中的其他组件的能力;即，通过渠道传播渠道（-end）引用的知识。这在MoCha是可能的。然而在这个124J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121我们将逻辑移动性定义为通过连接和断开操作改变系统中组件之间的通道连接MoCha支持物理和逻辑移动性移动性允许动态重新配置应用程序中组件之间的通道连接，这是一个非常有用的属性，甚至在组件可移动的系统中至关重要在分布式系统中，当一个组件可以从一个位置（其代码执行的位置）移动到另一个位置时，它被称为移动组件因为通过通道的通信也是匿名的，所以当通道端移动时，通道另一侧的组件不知道也不会被这种移动所干扰渠道提供透明的外部协调。 通道允许组件之间的几种不同类型的连接，而不需要知道它们处理的通道类型。只有连接的创建者才知道通道的类型。这使得从外部（外部）协调组件成为可能，因此，无需更改其组件的代码即可更改应用程序3Petri网Petri网实际上是一类基于网络的模型的通用名称，可以分为三个主要层[17]。第一层是最基本的，特别适合于深入研究并发系统的基础问题。这里的基本模型是基本网络系统[16]或EN系统。第二层是一个这里的基本模型是放置/转换系统[2]，或P/T系统。最后，第三层是高级网络，其中使用基本代数和逻辑工具来产生适合于现实生活应用的“紧凑网络”。谓词/变迁网[5]和有色Petri网[10]是最著名的高级模型。以上三层的任何Petri网都适合对系统建模。此外，任何层的任何Petri网都可以转换/转换为另一层的Petri网[4]。翻译的例子在Engelfriet[3]和Jensen [11]的工作中给出我们使用Place/Transition Petri Nets指定了MoCha框架的所有通道类型与高级Petri网相比，这类Petri网处于正确的抽象层次，具有明确的不可改变的语义规则和结构。然而，在本文中，为了简单起见，我们使用基本网系统Petri网。最后一种Petri网更容易使用，因为它们的理论更简单。此外，两种模型的同步通道类型的拓扑结构J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121125结构等同。对于本文中介绍的异步类型，3.1基本网络系统本文简要介绍了基本网系统（简称EN系统我们只限于本文所需的定义。对于广泛的介绍，也涵盖了EN系统的几个属性，等价物，EN分析，我们参考教程[17]。网是所有Petri网的最基本定义：定义3.1一个网是一个三元组N=（P，T，F），其中（1）P和T是有限个网，其中P≠T=N，(2)F（P×T）（T×P），(3) 对每个t∈T，存在p，q ∈P使得（p，t），（t，q） ∈F，且(4) 对任意t∈T和p，q∈P，若（p，t），（t，q）∈F，则pq.P的元素称为位置，T的元素称为变迁，X=P<$T的元素称为（N的）元素，F称为（N的）罗夫关系每一个位置p∈P都可以被看作是系统的一个可能的局部状态。在每个时刻，一组局部状态（地点）参与系统的全局状态我们把这样一组位置称为配置。从图形上讲，我们用一个标记来表示配置的一部分;一个黑色的小圆圈。定义3.2网N=（P，T，F）的构形C是P的子集。因此，网的配置C是P的子集，其中每个位置包含一个令牌。我们现在定义一个基本的网系统，如[17]所示定义3.3定义：EN系统是一个四重M=（P，T，F，Cin）其中：(1)(P，T，F）是一个网，(2)CUP中的C是初始配置EN系统中的每个转换都可以执行一个称为fire的动作。该操作从所有输入位置获取一个标记，并将一个标记放置到转换的每个输出位置。此操作表示系统的连续步骤。然而，要做到这一点，转换的所有输入位置必须有一个标记，其输出位置必须为空，因为一个位置最多只能同时有一个标记。126J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121定义3.4设M=（P，T，F，Cin）是EN系统，且t∈T.(1) ·t是t的输入位置，t·t是t的输出位置。(2) 设C是一个配置。则t在C中有让步（或t可以在C中被触发），如果·t∈C且t·∈C=π，则设为tconC。(3) 设C，D为P。则t从C到D发射，如果t con C且D=（C−·t）<$·，写为C[t > D; t也称为从C到D的顺序步骤。4基于移动信道的系统为了对使用移动信道的系统进行建模，我们需要在Petri网中对信道进行建模，从现在开始，首先是PN。然后，我们将组件的PN与我们的移动信道的PN组合在一起。其次，我们给出了这些PN移动信道的接口。 然后，我们给出组件使用通道所需实现的接口和最小行为。然后，我们指定PN复合函数σ。除了组合之外，该函数还隐式地对连接和断开通道操作进行建模（也使用反函数）。最后，我们给出EN系统的一组代表性的移动信道类型。4.1移动通道接口我们在本节中介绍的EN和P/T-net移动信道系统从系统组件的角度来看都具有相同的接口。我们在图2中给出了这个接口。每个通道网络都有一个由其类型决定的内部部分我们通过在圆的外侧标记一个额外的符号I来图形化地表示这些地方。接口位置是协议的一部分，以确保所有的写和取操作都是阻塞的;即，执行这样的操作的活动实体阻塞，直到操作成功并终止。图二. PN移动信道接口该应用程序是一个软件包， PWA 构造S形通道端部的内表面。想要在这一端执行写操作的组件将一个to_k_in放置到plac_p_S_o_r_c。此存储表示数据元素可用，但尚未被通道接受。换句话说就是p源pWA我我源信道水槽我我pRTTp水槽J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121127写操作在组件和源通道端之间挂起。当令牌被通道从这个地方移除时，这意味着通道正在处理写操作。 在操作完成时，通道将一个字放在接口平面PWA中;一个字被写入。PLASINK和PR TT 构成油墨通道端的内表面。想要在这一端执行take操作的组件，PRTT（准备好了）。 这将消除组件从信道获取数据元素的期望和意愿。但是，通道知道有一个组件正在等待（并希望）在其处于优先级R T T时获取元素 成功的话，你就可以通过火灾来控制通道了。通道通过将令牌in放置到pSink来终止take操作 在接口板上。 公司不能让他离开这个地方。我们没有明确的模型的源-和汇-结束在移动渠道网。一个通道端是隐式地由它的两个接口位置和内部转换来建模的，这些位置是输入或输出。注意，write和take操作的语义与[8]中定义的语义类似。4.2组件交互系统的组件通过我们上面定义的接口与移动通道交互。从渠道的角度来看，组件由一个或多个执行写和取操作的活动实体（线程或进程）组成。在图3中，我们给出了两个单一实体组件的EN系统。它们表示组件需要实现的关于对通道的写和取操作的最小行为;即，它们实现第4.1节中描述的阻塞协议的它们的一侧。图3（a）显示了一个简单写入器的PN。该网络具有两个接口平台，用于与CHAN进行通信：{pOutput，pWA}。网络的初始配置是{p2}。写入器通过执行{p2}[t2>{pOutput，p1}开始写入操作。在该点处，它被封锁 ， 因 为 它 必 须 在 接 收 到 书 面 知 识 之 前 被 封 锁 ; 即 ，AtokennisplacedinpWA. 我相信写入器在接收时与源通道端交互众所周知，在平面图中， 已经准备好了。 对于e，我们以配置{p1，pWA}结束。作者通过执行序列步骤{p1，pWA}[t1>Cin. 在这一点上，我可能不会再写了。图3（b）显示了一个简单的接受者的PN该网络还具有两个接口平台，用于与CHANN进行通信：{pInput，pR TT}。 THE128J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121p输入我pRTT我p p输出WA(a) 作者（b）接受者图三.一个写作者和一个接受者EN系统这个网的初始配置是{p2}。接受者通过执行{p2}[t2>{p1，pR TT}开始接受操作. 在某个时间点上，通道与PR TT的token交互，然后，它将token back放在PInput的适当位置。 其结果是：{p1，pInput}。通过构造{p1，pInput}[t1>Cin. 在这个地方，我可能不会再服用了。4.3部件和通道我们介绍了通道的接口和组件对通道的接口。我们现在需要将组件和通道组合在一起。有几种可能的构建策略。我们的主要要求是这种策略是组合的。人们应该能够区分组合系统中的各个组件和通道，并且必须易于分解和重新排列系统;即更新和替换组件和通道，而不必更改系统的其余部分。因此，例如，我们不能进行合成并优化所得PN，因为在许多合成步骤之后可能不再可能分解。因此，我们的策略是在接口位置上进行合成。这样，我们很容易识别各个部分。而且，分解也很清楚，很容易做到。为此，我们定义了一个组合函数，它合并或连接接口位置：定义4.1我们定义复合函数σ：（X1，P1，X2，P2）−→在哪里，(1) X1、X2和Y是EN系统(2) P1和P2是有限的空间，其中P1是PX1，P2是PX2，t1p1p2t2我我t1p p1 2t2J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121129|为|P 2|.|.这些集合的典型元素是p1∈P1和p2∈P2.我们构造新的Petri网EN系统Y如下，(3) 我们重新命名了网X1和X2有相同的名字。(4) PY=（PX1\P1）（PX2\P2）Pnew，其中<$（pairs（p1−i，p2−i））<$pnew−i∈Pnew，其中i作为从1到|P1|为|P2|得双曲正弦值. |P1|为|P2|为|P新|、(5) TY=TX1<$TX2，(6) FY=（FX1<$FX2<$FI）\FRem，其中n（i∈1too|PK|）if（pk−i，t）∈FXk n（pk−i，t）∈FRem（pne w−i，t）∈FI，n（i∈1too|PK|）if（t，pk−i）∈FXk n（t，pk−i）∈FRem（t，pne w−i）∈FI，其中k ={1，2}，p k−i∈P k且p new−i∈P new，都具有索引i。(7) Cin−Y=（Cin−X1\P1）<$（Cin−X2\P2）<$Cin−new，其中（i∈1too|P新w|）如果pk−i∈Pk<$pk−i∈Cin−Xk npne w−i∈Cin−new，其中k={1，2}。函数σ将EN系统作为参数，X1和X2。该函数还采用两组位置，P1和P2，分别对应于我们想要合成的X1和X2该函数的结果是一个新的EN系统Y，它的构造如下：（3）对网X1和网X2中由于组合而引起名称冲突的所有位置、变迁和关系流进行了（4）X1和X2的每个位置都存在于Y，除了P1和P2的接口位置。这些位置中的每对{p1，p2}由于具有相同的索引号而彼此相关，替换插入Y中的新位置pnew。 (5)合成是在接口位置上完成的，因此Y的转换只是X1和X2中的转换的并集。(6)存在于X1或X2中的每一个关系也存在于Y中。涉及P1和P2中的接口位置（用FRem表示）的流关系被改变为涉及点3的新添加的位置（用FI表示）。 (7)Y中的C是X1和X2的并集。然而，P1和P2的位置也可能出现在这两个最后EN系统的初始配置中。由于这些位置在Y中不再存在，我们将它们对应的新位置从Pnew添加到初始配置中。我们现在可以使用函数σ来组合组件和通道。例如，我们通过将σ函数应用于写者、接受者分量和通道（我们先前定义的）来获得图4的PN系统Comp：σ（W riter，{pOutput，pWA}，Channel，{pSurce，pW A}. 我不是他的形象，一般频道定义。 之后，我们给出了几种不同的PN-系统，130J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121我写不我WA源我我tWT1tWT2p1p2t1t2我我见图4。用移动渠道ppppWA来源pI3p水槽我pRTTpRTTp水槽(a) 同步信道（b）有损同步信道图五、同步与有耗同步信道EN系统移动渠道类型。复合函数σ隐式地对连接操作进行建模。我们的组件然而，如果一个组件与一个通道由σ组成，我们认为这个组件连接到适当的通道端。类似于连接，我们隐式地用函数σ−1（σ的逆）来建模断开。4.4一组EN和P/T-net移动信道系统我们现在采取了一组有代表性的移动信道类型，并给出了EN系统为他们每一个。t1p1p2t2p源输出pWA源信道水槽p水槽输入pRTTt3p3p4t4J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）1211314.4.1同步通道类型使用同步通道，两端的I/O操作是同步的; I/O操作原子地成功。图5（a）示出了该通道的EN系统。这个通道类型的内部只是一个转换tWrite，它包含了4.1节中定义的四个接口位置。我们的地方 PR TT 是转变tW rite的输入位置。因此，只有当写入和获取组件都已各自将令牌插入到会话中时，在这些位置上，I/O操作自动成功（同时）;每个组件将一个令牌插入到其对应的位置，如第4. 二、 我们给出了序列迭代步骤：{pSorce，pR TT}[tWrite>{pSink，pWA}。Ateendatokenisinsertedd id id inhe spSink 和pWA. 从通道的角度来看，这些指示I/O操作的结束。4.4.2有损同步信道类型对于有损同步通道，如果在向源端写入值时没有在接收通道端执行I/O操作，则写入操作总是成功，但值会丢失。在所有其他情况下，通道的行为类似于正常的同步类型。图5（b）给出了这种通道类型的EN系统。成功的写操作有两条路径。一种是由tWT1跃迁决定的，表现出同步信道的行为。另一种是由tWT2跃迁决定的，表现出有损耗的特性.在第一或第二路径之间的选择取决于是否存在等待取值的组件，这由在placepR TT中的a to k e n的概率来确定。然而，该频道尚未意识到这一意图。只有在发射转换t1信道是否知道组件准备好接受值：{pR TT}[t1>{p1，p2}。如果在placepsoure中有一个to ken，这里有一个组件正在尝试写入，当在位置p 1和p 2中有一个token时，transition t WT 1会触发;有一个组件等待take。同时，由于令牌在位置p2，转换tWT2被阻塞。因此，写入的值从pSorce同步地向pSink：{pSorce，p1，p2}[tW T1>{pSink，pWA}。但是，如果在位置p1和p2没有标记，则没有组件transitiontWT2触发，当写操作成功时，值丢失观察到，由于在p1处缺少令牌，转换t WT1无法触发。不需要为垃圾收集器建模来删除令牌值，因为转换 t2的触发已经处理了这一点。给出了 损失路径的序列步数：{pSorce}[tW T2>{p2，p3}[t2>{pW A}.132J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）1214.4.3FIFO和FIFO n通道类型ppWA来源ppWA来源ppWA来源我pRTTp水槽我pRTTp水槽pRTTp水槽(a) FIFO−1（b）FIFO−2（c）FIFO−n见图6。 FIFO 1、2和n通道EN系统对于异步FIFO通道类型，在两个通道端执行的I/O操作以异步方式完成。写入源通道端的值在内部存储在缓冲器中，直到从接收端取出。图6（a）显示了FIFO-1通道的EN系统。正如人们所期望的，容量1的内部缓冲器由位置pbuf建模。 我们通过执行以下等式为渠道创造价值-初始值{pSorce}[twrite>{pbuf，pWA}，并通过执行{pbuf，pR TT}[tTake>{pSink}。 图6（b）我们将创建一个FIFO-2EN系统通道。 当然，它包含两个更大的地方。 图6（c）给出了一般的一种缓冲器容量为n的FIFO EN系统通道方案。 注意，如果n是无限的，无限FIFO通道类型，我们得到一个具有无限位置的EN系统。为了避免这种情况，我们使用P/T-net系统，其中我们有一个容量无限的单一存储器。然而，出于节省空间的原因，我们在本文中省略了这种PN4.4.4异步漏极通道类型异步漏极沟道类型具有两个源极沟道端。此外，在该通道的末端上执行的I/O操作一次仅一个地成功。所以它两端的写操作永远不会同时成功。这反映在我们在图7（a）中给出的网络中。地点P3我我写不pbuf受不了我我我写不pbuf1t1pbuf2受不了我我我写不pBuf（1）tbuf（2−n）pbuf（2−n）受不了我我虚线模式重复，直到有n个buf位置J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121133pWA1pSource1p源2pWA2我t1pRTT−1p水槽-1p水槽-2pRTT−2(a) 异步排水（b）异步喷口见图7。非同步排水和排水EN通道系统确保transitiontWrite1或transitiontWrite2触发，但不能同时触发。让我们假设有两个同时可用的写操作;净配置为{ p s o r c e 1，p s o r c e 2 }。 然后，我们可以首先执行对源代码的写入操作：{ p sorc e1，psorce2}[tWrite1>{p s o r c e 2，p 1，p 3 }，阻止了该配置转换tW rite2，{psorce2，p1，p3}[t1>{psorce2，pW A1}。或者，我们可以在源端的右首执行写操作{psorce1，psorce2}[tWrite1>{psorce1，p2，p3}，该构型转变tWrite1被阻断，{psorce1，p2，p3}[t1>{psorce1，pWA2}。然而，我们不能同时执行两个写操作，因为我们不能触发转换t同时写入1和24.4.5异步喷口通道类型异步喷口通道类型具有两个汇通道端。此外，在该通道的末端上执行的I/O操作一次仅一个地成功。所以两端的take操作永远不会同时成功。这反映在我们在图7（b）中给出的网络中。Placep2确保transitionttake1或transitionttake2触发，但不能同时触发。让我们假设有两个同时可用的拍摄;净配置是{ pR T T 1，p R T T 2 }。然后，我们可以首先在左汇上执行捕获操作：{pRTT1，pRTT2}[t1>{pRTT2，p1，p2}，在此配置中，平面p2中的tokn阻塞了transitiont2的触发，{pRTT2，p1，p2}[tTke1>{pR TT2，pSink1}。或者，我们可以在k中的s上执行take operation，并在righttst：{pRTT 1，pRTT2}[t2>{pRTT1，p2，p3}上执行takeoperation，在placep2中执行takeoperation阻塞了transitiont1，{pRTT1，p2，p3}[tTake2>p1p2p3tTake1tTake2t2我我我我我我我t写入1t写入2p1p3p2t1t2134J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121{pR TT1，pSink2}。 然而，我们不能同时执行任务，因为我们不能同时执行任务1和任务2的转换。5分析和仿真我们现在知道如何通过Petri网对使用我们的移动信道的系统进行建模。在本节中，我们将讨论这些模型的分析和模拟。图8模拟了一个由4.2节中定义的写和取组件组成的系统。这两个组件通过一个有损同步通道进行交互，如4.4节所定义。我们通过函数σ将每个独立实体的Petri网组合起来得到系统：σ（Taker，{pInput，pR TT}， T mp，{pSink，pR TT}），Tmp=σ（W riter，{pOutput，pWA}，-损失ySynchronous，{pSource，pWA}.见图8。 组成的一个例子我们可以通过玩“代币游戏”来模拟这个系统。这个游戏由触发转换组成，在可能的情况下，使系统从一个状态进入另一个状态。如果我们覆盖了所有可能的触发序列，我们就得到了系统的所有可能状态，从而得到了这个系统的所有可能的外生协调在图9中，我们给出了图8的顺序配置图。对于（顺序）配置图的精确定义，请参见[17]。除了仿真，我们还可以分析模型的外生协调对Petri网进行了广泛的分析。最常见的分析特性包括因果关系、并发性、冲突、混淆、死锁和等价性。第一，研究系统中事件之间的因果关系。第二，分析哪些系统事件在同一时刻并发。第三，分析哪些事件在同一时刻发生。并发和冲突之间的诡辩交互可能导致第四种混乱;并发事件可能成为冲突事件，反之亦然。前四个特征使我们能够推理，第五个，tw1pW1pW2tw2pWAp源tWT1tWT2p1p2p3t2t1p水槽pRTTtt1pT1pT2tt2J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121135Tw2Tt2TWT2TT2{Pw2，Pt2} =（1）TW2（2）={Pw2，Pt1，Prtt}{Pw1，Psource，Pt2} =（3）T1(4)={Pw2，Pt1，P1，P2}{Pw1，Pt1，Psource，Prtt}{Pw1，Pt2，P2，P3} =（5）TW2T1{Pw1，Pt1，Psource，P1，P2}Tt2 Tt2{Pw1，Pt1，Prtt，P2，P3}T2T2{Pw1，Pt2，Pwa}（6）={Pw1，Pt1，Psink，Pwa}{Pw1，Pt1，Prtt，Pwa}T2T1（一）{Pw2，Pt1，Psink}TW2TT1{Pw1，Psource，Pt1，Psink}（一）{Pw1、Pt2、Pwa}TW1{Pw1、Pt1、P1、P2、Pwa}中文（简体）（二）(3){Pw1，P2，P3，Pt1，Psink}TT1T2(5)（六）见图9。图8的顺序配置图系统中的死锁。最后，Petri网分析包括等价性。通常，系统的相似性是建立在态射的概念上的例如，我们可以分析示例模型的外生行为以找到并发步骤。为此，我们可以看看它的顺序配置图，如图9所示。 基本上，图中的每一个钻石形状都代表着 并发 步第一个 可能并发 步是{pw2，pt2}[{tt2，tw2}>{pw1，pt1，psurce，prtt};我们可以从配置中到达{pw2 ， pt2} 到 配 置 {pw1 ， pt1 ， psorce ， prtt} ， 通 过 初 始 化transitiontw2和thentransitiontt2，或使用vice-versa。关于一致性的精确定义和其他分析，我们参考[17，2]。6复杂性和对工具我们在图8中建模的系统非常小和简单。“手工”分析和模拟这个系统是可能的，但已经不是一个令人愉快的任务。例如，看看图9的大小。一个TW1TWT 1TT2TW1TW1TT1TT1TWT2136J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121真正的应用程序包括有许多组件和许多移动渠道。因此，对这样一个应用程序建模很快就会产生一个非人类的大型Petri网模型J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121137不再温顺原因之一是我们选择的构造策略是compo- sitional（参见第4.3节）。因此，我们无法优化我们获得的PN系统，因为这样我们就无法识别其组成部分了。然而，这种爆炸性增长的主要原因是EN和P/T系统不支持高级结构，如约束。这迫使我们明确地实现我们需要的一切。例如，我们显式地实现了一个用于对阻塞操作进行建模的协议（参见第4节）。如果我们的目标是生成人类可读的模型，那么，我们在本文中使用EN和P/T系统的方法并不真正适合。 例如，更好的选择是像着色Petri网[10]这样的高级Petri网，或者使用[8]中给出的MoCha-pi演算。然而，我们的方法产生的Petri网模型非常适合使用工具进行验证和仿真。这是因为EN和P/T系统具有明确的不可更改的语义规则和结构，并且我们的Petri网模型显式地编码了低级技术细节，否则这些细节不会被指定。幸运的是，有许多工具可用于EN和P/T系统。对于这些工具的广泛列表，我们参考了[13]中的最新工作。我们正在试验平台无关的Petri网编辑器（PIPE）工具[1]。我们选择这个工具是因为，它是免费的，平台无关的，O模拟和分析模块，并给出XML支持。7结论在本文中，我们展示了如何对通过移动信道进行通信并由移动信道协调的分布式系统进行建模。 我们专注于这些系统的外生协调建模。这样的系统的例子是基于组件和P2P网络，如[6，7]中所解释的。我们选择使用的建模语言是Petri网。我们讨论了组件的建模，移动通道和它们的组成到分布式系统。我们讨论了这些Petri网模型的分析和仿真。 特别是分析了这些模型的因果关系、并发性、冲突、混淆、死锁和外生协调的等价性我们还讨论了我们将MoCha映射到Petri网的方法的消极和积极点。在消极的一面，我们产生的模型很快就变得难以处理。 从积极的方面来看，这些模型的低级语义使它们非常适合使用我们使用的Petri网的许多工具Petri网已被应用于许多不同的应用领域。因此138J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121在建模领域有高度的专业知识。本文感兴趣的是[9]中提出的Web服务组合工作。MoCha通道适用于Web服务，我们打算使用本文的通道Petri网，以及这一目的。在[14]中，Petri网被用来对分布式算法进行建模。虽然我们没有引入明确的位置概念，但我们的通道Petri网定义了MoCha框架通道类型的分布式实现。引用[1] J.D. Bloom，平台独立的Petri网编辑器（PIPE），电子手册，2005年，可在http://petri-net.sourceforge.net在线[2] J. Desel和W.Reisig，Place/Transition Petri Nets，Lecture Notes in Computer Science，Vol.1491：Lectures on Petri Nets I：Basic Models，pages 122-173.Springer-Verlag，1998.[3] J. 张文龙，Petri网的分支，信息学报，第28卷，第6期，第575 - 591页，Springer-Verlag，1991年。[4] J. Engelfriet，Private Correspondence，LIACS，2004.[5] H. J. Genrich，谓词/变迁网，Advances in Petri nets 1986，Part I on Petri nets：CentralModels and their properties，第207 - 247页，Springer-Verlag，1987年。[6] J.V. Guillen-Scholten，F. Arbab，F.S. de Boer和M.M. Bonsangue，一个基于构件的协调模型，A。Brogi和J. Jacquet，编辑，第一届协调语言和软件架构基础国际研讨会论文集，ENTCS68.3，Elsevier Science，2002。[7] J.V. Guillen-Scholten，F. Arbab，Coordinated Anonymous Peer-to-Peer Connections withMoCha，Proc.第四届分布式Java应用程序科学工程国际研讨会（FIDJI 2004），卢森堡，2004年11月68-77，Springer-Verlag，2005年1月。[8] J.V. Guillen-Scholten，F.Arbab，F.S.de Boer和M.M.Bonsangue，MoCha-pi，基于移动信道的外生协调演算，2005年ACM应用计算研讨会论文集，圣达菲，新墨西哥州，美国，2005年3月13日至17日[9] R. 哈马迪湾张文，一个基于Petri网的Web服务组合模型，第十四届澳大利亚数据库会议论文集，第17卷，第191 - 200页，澳大利亚，2003年。[10] K. Jensen，《有色Petri网简介，系统构造与分析的工具与算法》。TACAS'97研讨会论文集1217，Springer-Verlag 1997。[11] K. Jensen，有色Petri网。 基本概念、分析方法和实际应用。第一卷基本概念《理论计算机科学专著》，Springer-Verlag，1997年第二次ISBN：3-540-60943-1。[12] C.A. Petri网，时间和空间。理论计算机科学，153：348，1996。[13] Petri Nets World，Petri Nets ToolDatabase，可在http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/网站，2005年[14] W. Reisig，Elements of Distributed Algorithms：Modeling and Analysis with Petri nets，Springer-Verlag，1998。[15] W. Reisig. G. Rozenberg（Eds.），《Petri网的基本模型》，计算机科学讲义，第1491卷，Springer-Verlag出版社，1998年。J. Guillen-Scholten等人理论计算机科学电子笔记154（2006）121139[16] G. 罗曾伯格，基本网络系统的行为，计算机科学讲义，第254卷，第60-94页，Springer-Verlag，1986年[17] G. Rozenberg和J.Engelfriet，Elementary Net Systems，Lecture Notes in ComputerScience，v. 1491，Springer-Verlag，12-121，1998。