马尔可夫过程代数理论：非乘积形式解决方案在随机建模中的应用及推广

理论计算机科学电子笔记151（2006）61-76www.elsevier.com/locate/entcs过程代数非乘积形式P.G. 哈里森1英国伦敦帝国理工学院计算机系摘要马尔可夫过程代数的反向复合代理定理的推广，产生可分离的，但非产品形式的解决方案，如出现在多类共享网络与处理器共享服务器的相互作用的过程的集合。它基于对多智能体合作状态空间中的最小循环的分析，可以简单地识别。扩展的方法导致我们认为是新的可分离的解决方案，更一般地说，结果代表了一个可行的实际应用的马尔可夫过程代数理论在随机建模。关键词：马尔可夫过程，反向复合主体定理，非乘积形式，随机建模1引言在随机网络中寻求所谓的平衡状态概率的乘积形式解已经成为性能建模的主要研究领域超过30年，例如[1，13，14]。 顾名思义，这样的解决方案被表示为项的乘积，每个项仅与交互组件进程的集合中的一个相关。大多数注意力都集中在网络及其变体上，如G网络[5]，但也有其他重要的例子。反向复合主体定理（RCAT）是利用马尔可夫过程代数（MPA）导出两个处于平衡状态的连续时间马尔可夫链之间某种合作从一个反向过程，加上给定的正向过程，联合状态概率作为这两个过程中速率比的乘积，当存在乘积形式时，产生乘积形式。因此，RCAT提供了一种替代方法，具有语法上可检查的条件，它统一了许多产品形式，超越了那些网络广告。1电子邮件：pgh@doc.ic.ac.uk1571-0661 © 2006由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2006.03.01262P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61本文提出了一个重要的推广，在其他网络中产生可分离的，但非产品形式的解决方案，其中一些转移率取决于一个以上的同步过程的状态。例如，这种情况出现在具有处理器共享（PS）队列的多类网络的推广是基于多智能体合作的状态空间中的最小周期具体地说，它表明，围绕任何周期及其逆周期的利率乘积之比，需要建立柯尔莫哥洛夫扩展的方法学导致我们认为是新的可分离的，非产品形式的解决方案和constiutes的随机建模工具的机械化的一个主要贡献在下一节中，回顾了马尔可夫状态转移图的基本背景材料及其与MPA的关系;附录中给出了MPA PEPA的基本定义本节还包括一个新的结果，它将用于我们的主要分析，涉及某些平行和同步过程。主要部分3考虑非本地状态依赖多智能体合作，并提出了一个较弱的版本RCAT，依赖于检查产品的最小周期周围的利率这导致Muntz和Palacios [1]处理器共享队列和新产品形式。本文件在第4节结束。2预赛2.1状态转换路径和拆分操作一旦已知了一个反向过程，当从一个选定的参考状态到所讨论的状态找到了一条合适的路径时，平稳马尔可夫过程的平衡概率的解一个组件中的动作α在合作中，我们说这个例如，队列中的服务完成（α+）可能导致外部离开或客户转移到另一个队列（α）。一般来说，一个动作可以分为两个以上的子动作，对应于多个同步，每个子动作都有一个明确的速率。反向的子动作被分配与它们的前向转换速率成比例的速率，它们的总和等于完整动作的反向速率（在隔离组件中）;参见[7]。如果每个合作只涉及每个组件中的子动作，而每个相应的完整动作的另一个子动作不参与，则总是存在从任何选定的参考状态（0， 0）到每个状态（i，j）的直线路径也就是说，P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6163为了简单起见，考虑两个组件的协作，只需在第一个组件进程中遵循从（0，0）到i的路径，第二个组件处于状态0，然后在第二个组件进程中遵循从0到j的路径，第一个组件处于状态i.然后，可以通过分别找到每个协作分量中的比率的乘积来找到可分离的解，其中RCAT给出了分量的重新参数化请注意，并行（非合作）代理是一个空重新参数化的特殊情况。2.2剩余诉讼我们可以保证直线路径确实存在，这是相同的级联的路径在孤立的组件过程中，通过增加积极的synchronising行动与残留行动或同步行动。这些与同步动作平行，但不参与合作。定义2.1假设（a，λ）是在某个主体P中的作用。 施事Pa+<$=P{（a，λ）<$（a，（1−<$）λ）}<$P{（a，λ）<$（a<$，<$λ）}对于某个实数<$，0<<$1，其中动作类型a<$不会出现在P中。剩余作用（a，<$λ）称为一个反作用。代理Pa+P b表示具有相同生成矩阵的马尔可夫过程，P的马尔可夫过程，但每个元素表示为行动类型a解释为数量（1−λ）λ（原始行动a）和λ λ（行动-行动）之和。也就是说，作为Pa+λ基础的马尔可夫过程具有与P相同的转变，除了a的速率减小1-λ的因子，并且存在与（具有相同的源和目的地状态），所有这些都由动作类型A表示。显然，lim→0Pa+ =P。我们不能假设任何关于遍历性和它在这个极限中的保持，但这在这里不是一个问题，因为所有的过程都假设是平稳的。遍历性条件需要单独分析。请注意，一个反向的剩余作用（a，λ）=（a，λ），也就是说，它的速率是和未分裂作用a的反向速率的乘积。在一个具有合作行动的行动者的合作中，我们必须在只使合作部分被动之前，将一个被动行动分解为剩余的和合作的部分为了简洁起见，我们表示一个代理P，其中一个动作类型a是被动的，通过P（a，T）<$P{（a，λ）<$（a，T）}，其中λ匹配到类型a在P中的动作的速率（在其每个实例中可能不同）。这个符号以明显的方式扩展到多个动作类型a∈S，每个动作类型在代理P{（a，λ）|a∈ S}。我们现在可以写Pa+T（a，T）来定义一个具有被动行为的修改的施事P类型a，拆分以引入速率为λ的平行剩余作用，其不同步，其中λ是P中a的速率（在每个实例中可能不同）。对于带有剩余作用的某些合作，我们有以下简单但重要的性质。64P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61R RRRSSRLRS引理2.2考虑没有被动行为的主体R，S，设R中的行为类型a具有速率λa，S中的行为类型a具有速率μa。设ra和ra是合作中a和a在a的特定实例处 的 比率Ra+βD Sa+（a，T）和Ra+（a，T）DSa+L其中a ∈ L. 然后ra=λaμa当且仅当μL=λ。a aaλaμa证据通过定义合作组合子和分裂类型为a的作用，ra=（1−λ）λa和ra=（1−λ）μa，因此结果如下。Q这个引理意味着包含合作动作的路径等价于不包含合作动作的路径，在平衡状态概率的意义上如下。引理2.3在前面引理的记法中，设r，r是利率的俄.西R，S中的剩余作用型a，设r_a，r_b为各自的逆俄.西率为1。然后，在a的特定实例处，rarr=R S当且仅当μa= λa。raa a证据 r=λa和r=λa。 同样，r=μa和r=μa，因此，因子在比率中抵消，结果由引理2.2得出。Q然后，假设协作动作类型a表示R D S中的状态（i，j）和（iJ，jJ）之间的转换;即它还表示R中的转换i→iJ和S中的转换j→jJ。L然后，路径（i，j）→（iJ，j）→（iJ，jJ），（i，j）→（i，jJ）→（iJ，jJ）（经由残差trans-t），（i，j）→（iJ，jJ）（通过同步转换）在意味着每条路径中每次传输的正向速率和反向速率的比率的乘积这是Ra+<$（a，T）DSa+<$D是Ra+<$D的逆过程Sa+（a，T），一个简单证明L对于RCAT。此外，它也可以用来寻找简单的可分离的解决方案直接满足该定理的合作的平衡态概率2.3多代理合作在PEPA合作PD Q，合作集中L相对于代理P是被动的（即具有未指定的速率T）的L表示为PP，相应的主动动作类型的子集表示为AP=L\PP;对于代理Q也是类似的。对于RCAT，还假设在P da Q中，任何主动动作L在P中有一个对应的被动作用在Q中，反之亦然;因此，PP=AQAP=PQ。在PEPA的扩展中，现在考虑多代理，成对合作ndak=1LPk（n≥2），其中L=nk=1Lk和Lk=Pk <$Ak是同步动作P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6165KKKK一在施事P k中出现的类型（表示PPk PK和APK Ak）。每个n个代理（最多）彼此合作，因此Pknj=1j/k=Aj和Aknj=1j/k=Pj。我们提供了多智能体合作的语义，定义它的条款，PEPAndak=1LPk=（.（（P1DP2）M2D P3）DM3M4 ...DMn−1 Pn−1）DPnMn其中Mk=Lk.k−1j=1ΣLj. 请注意，在用于蝴蝶结符号的微妙变化多Agent合作。2.4符号我们将使用以下符号，推广[10]的符号i→表示Lk中的动作类型的集合，这些动作类型在Pk中是被动的，并且对应于在Pk的马尔可夫过程中从状态i转移出来;i←表示Lk中的动作类型的集合，这些动作类型在Pk中是被动的，并且对应于在Pk的马尔可夫过程中过渡到状态i;i→表示Lk中的动作类型的集合，其在Pk中是活动的并且对应于在Pk的马尔可夫过程中从状态i转移出来;i←表示Lk中的动作类型的集合，这些动作类型在Pk中是活动的并且对应于在Pk的马尔可夫过程中过渡到状态i;Pi→表示L中的动作类型的集合=nk=1Lk是被动的，n对于从状态i =（i1，i2，.，in）在马尔可夫过程中，dak=1LPk;Pi←表示L中的动作类型的集合，这些动作类型是被动的并且对应于trans-i。n进入状态i的马尔可夫过程dak=1LPk;Ai→表示L中活动的并且对应于transi的动作类型的集合n在马尔可夫过程中，dak=1LPk;Ai←表示L中活动的并且对应于transi的动作类型的集合n进入状态i的马尔可夫过程dak=1LPk;i表示马尔可夫过程中状态i的瞬时转移率n的dak=1LPk对应主动作用类型a∈L;Ta表示动作（a，Ta）中与动作类型a相关的未指定比率;x表示向量（xa1，.，xam）的正实变量xai 当L=PP一一α66P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61一k;a{a1，. ，am};βi（x）表示反向马尔可夫模型中状态i的瞬时转移率过程ndak=1LPk{Ta←xa|a∈L}对应于被动作用类型a∈ L;注意，在转发过程中，A进入状态i我们也写βik（x）<$βi（x）其中P是其中a是被动的（进入状态i）的分量阿k k3非局部状态依赖从RCAT产生的逆过程和乘积形式需要在[7，10]和下面的定理3.7中给出的条件，以确保Kolmogorov这些标准是：(i) 从每个状态的总输出速率（平均状态保持时间的倒数）在正向和反向过程中是相同(ii) 马尔可夫状态转移图中每个周期周围的速率的乘积在正向过程和反向过程中是相同的对RCAT证明的检验表明，即使是状态相关速率（Hillston称为然而，柯尔莫哥洛夫的第二个标准一般不成立。因此，一个较弱形式的RCAT与函数率的合作将读取完全相同，但需要检查正向和反向过程中相应周期周围的率的乘积是否相等。要得到柯尔莫哥洛夫3.1最小循环为了证明正向过程和反向过程中每对相应循环周围的速率乘积的相等性，实际上只需要确定最小循环并证明它们周围的相等性最小圈的定义如下，它们的数量（也在下面给出）远远小于所有圈的数量，这可能是无限的。因此，当组件进程中的最小循环数很小且数量很少时，单独检查循环的前景是非常可行的定义3.1生成矩阵为Q的马尔可夫过程中的一个循环是一个转移序列{i0→i1，i1→i2，.，in−1→in}，缩写为i0→i1→... →in−1→ in，其中n ≥ 1且in= i0。一个循环是真的，如果ij/= ik，对于j/= k，1 ≤j，k≤n−1。 循环i0→i1→. →in−1→i0和j0→j1→. →jm−1→j0，其中j0=ik，对于某个k，0≤k≤n− 1是圈 我0 →i1→. →ik→j1→. →jm−1→ik→ik+1→. →in−1→i0.最小循环是不能表示为以下组合的真循环：P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6167更小的周期我们所关心的合作满足这样一个条件，即每一个主动行动的反向速率在其所有实例中都是相同的。因此，定理3.7的代理Rk成对地满足引理2.2和2.3。现在考虑在具有剩余作用的代理人的合作中，围绕周期的速率的乘积的比率，nndak=1L Rk{（a，T）|a∈ Pk（Lk）}， dak=1L Rk{（a，T）|a∈ Ak（Lk）}其中Rk表示代理Rk，其中所有动作都已被剩余动作分割，这里，不需要考虑同步过渡;这些过渡可以由仅在一维中的适当的直线过渡对代替，对应于各个同步分量。定义3.2由合作定义的马尔可夫过程中的直线循环是cycle，其中该直线循环由a∈/L的作用决定;即，由一个独立的动作发生在一个单一的组成部分，并不同步。平凡（直线）循环是其中所有转换都在相同维度中的循环即，由全部仅在一个组件中发生的动作来表示，其它组件过程的状态保持不变。在n个分量的协作中，令C1，.，Cn是每个不同分量过程中的最小循环。 基本周期(with 关于C1， ，Cn）是一个非平凡的直线圈，其中每个变迁都由一个作用表示，该作用的类型在极小圈Ck，1 ≤k≤ n中的一个中.通过前面的观察，在检验Kolmogorov准则的第二个时，只考虑RCAT-合作中的直线极小圈是足够的请注意，直线循环是每个组成过程中循环的乘积。这些组成循环中的一些可能是空的，即没有过渡;当除了一个组成循环之外的所有组成循环都为空时，直线循环是平凡的。它是简单的构造基本循环的合作从给定的最小循环的组件过程中，使用组合算法，很容易机械化。其数量由以下结果给出命题3.3 n个分量与m1，. ，m，n个最小循环，分别从状态空间中的给定状态开始，（m1 +. +mn）！m1！...，mn！其中m1 +... + mn是平凡的。证据 考虑一个2组件协作，并假设在协作的每个状态下都启用了每个周期中的所有（表示转换的动作）。然后，如果一个周期开始于它的一个给定的过渡，基本周期的数量，当一些动作被禁用时不能超过，是排列m1+m2个对象的可区分方式的数量，其中m1是白色，m2是黑色，即。2c|L|Cmc严格地说，它递归地定义为Rk = Rk，其中Rk=RkRk，L ={a1，. .，一|L|}。对于1 ≤m≤|L|，Rk =68P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6112⎛ ⎞m1+ m2m。其中包括全黑或全白的m+mM1在循环中连续发生-对应于平凡的直线循环。通过归纳，本文的论证简单地推广到n≥2的n-分量合作. Q本节的主要结果是确定了合作社的最小圈作为其基本圈。我们首先定义一个周期中可能出现的拐点定义3.4在状态i处的角点是一对连续的状态转移，它们发生在合作的两个不同的组成过程Pj，Pk中，例如：一个小时一个是“垂直”，一个是“垂直”。右上角，表示为|，由连续的转移ij：−a→i→ik：−b或ik：−c→i→ij：−d组成，其中ij：−a=（i1，.，ij−1，ij−a，ij+1，. ，in）在n-分量合作中。左下角表示为[，右下角表示为[，左上角表示为[，]，定义类似于|- 角落命题3.5基本圈是合作的最小圈。证据首先，平凡的基本循环显然是最小的。接下来，在一个非平凡的基本循环中，考虑由其中一个协作组件中的动作表示的转换。根据基本的定义，这些必须包括该组件过程中的最小循环。因此，每个基本周期都是最小的。为了证明相反的情况，考虑一个任意的有限循环A，它是两个分量的配合。我们表明，如果这不是一个基本的循环，它是一个简单的，最终基本的，循环的组合。我们用非负整数来枚举合作系统各组成部分的状态，在二维空间的右上象限。我们定义z（A）的大小，Σa cycleA byz（A）=（i，j）∈Ai+ j.在任何循环中，连续跃迁的方向以2π的非零倍数改变。每个角贡献±π/2的变化，因此每种类型的角必须在循环中出现相同的次数c>0次。 考虑一个|角点（比如说），包括（不失一般性）跃迁（i，j-1）→（i，j）→（i-1，j），比如说，i，j>0。假设子过程1中的转移i→i−1在该过程的循环C1中，类似地，转移j−1→j在子过程2的循环C2 现在设一个直线循环C包含|角落并且精确地由循环C1和C2中的所有转换（由动作表示）组成。则A是某个圈AJ和C的合成.此外，z（AJ）0，所以最终必然导致平凡循环AJ。但根据假设，平凡循环是一个组成过程中的最小循环的组合，这些最小循环与另组件进程这就完成了两个分量合作的证明。现在，通过根据两个分量的合作对多重合作本身的归纳定义，对n≥2个分量的合作进行归纳，得出QP.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6169一α一Kolmogorov因此，任何直线循环都是极小（直线）循环的组合，因此，为了验证具有状态相关速率的较弱定理3.7，只需直接考虑基本循环;与状态无关的情况相反，这些情况自动满足Kolmogorov准则的第二个3.2更弱、更通用的多代理RCAT在陈述主要定理之前，RCAT扩展到多个代理和功能速率，我们首先使状态依赖速率的概念更加严格。定义3.6合作的分支Pk（1≤k≤n）中的作用（a，λndak=1Lj=/如果λ依赖于{Pj}的至少一个导数，则Pk具有函数速率|k}。动作类型a可以在协作集合L中，也可以不在协作集合L中。在用功能速率合作表示的马尔可夫过程中，对应于具有功能速率的动作的转移是状态依赖的。一些这样的合作仍然有可分离的平衡态概率，如下所示：定理3.7（WMARCAT）n假设合作dak=1L代理Pk的Pk，具有功能速率，具有导数-图G的一个不可约子图，且对1≤k≤n，• Rk= Pk{Ta←xa|a∈ Pk（Lk）};• 每个反作用的实例，类型a，主动作用类型a∈Ak（Lk）在Rk有相同的速率ra;• {xa}是速率方程xa= ra，a ∈ L的唯一解.则代理ndak=1LRk{（a，T）|a∈ Ak（Lk）}导子图中含有反向子图G的，是反向施事ndak=1LPk，如果(i) 每个反向动作的每个实例具有相同的速率（如上所述）;Σ(ii)Xaa∈Pi→Σ-xaa∈Ai←Σ=a∈Pi←\Ai← βi（x）− βia∈Ai→\Pi→(iii) 中每个非平凡基本圈C周围的转移率的乘积n马尔可夫过程表示为dak=1LPk等于跃迁的乘积马尔可夫过程中相应的反向周期C周围的速率表示为n按dak=1L Rk{（a，T）|a∈ Ak（Lk）}.;70P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61此外，假定合作集L是有限的，则合作有可分离的解nπ（i）<$ πk（i1，. ，ik，0，. 、0）的k=1对于状态i =（i1，. ，in），其中πk（i）是成比例的当每个其他组成过程j/= k的状态固定在ij时，由R k表示的过程中状态i k的平衡概率。证据证明满足Kolmogorov准则的第一个准则的证明第二个标准通过前面一节的分析得到了满足--注意，我们不需要考虑平凡（基本）圈，因为这些圈通过假设每个主体Rk是已知的来满足它。对于定理的第二部分，我们考虑从状态0到状态i的直线路径，遵循顺序为1，2，.的状态空间维度。，n. 在维度k的路径段中，前向速率与反向速率的比率则为（通过假设）πk（i1，.，ik，0，.，0），结果如下。Q3.3速率依赖于状态的混沌网络考虑一个M节点Jackson网络，其中每个队列的服务速率取决于任意队列的长度。 假设M个节点具有各自的恒定外部到达速率λ1，... ，λM，状态相关服务率μ1（i），. . ，μM（i）在状态i =（i1，.，iM），以及从节点i到节点i的路由概率p ijj（1≤ij≤M），其中pii= 0。任务从节点i离开网络，概率pi0CIMMj=1 派伊杰.我们不考虑从一个节点返回到因为这被认为是组件过程定义的一部分，node. 这样的偏离可以很容易地包括在更复杂的组件中。M该网络在PEPA中很容易指定，功能速率为：其中，对于1≤k≤M：Pk，n=（ek，λk）Pk，n+1n≥0dak=1LPk，0（开始-Pk，n=（ajk，Tjk）Pk，n+1 n≥0， 1≤jPk，n=（dk，pk0μk（i））Pk，n−1n >0k≤MPk，n=（akj，pkjμk（i））Pk，n−1n>0， 1≤j/ =k≤M其中Lk={akj|j/= k}{ajk|jk}。功能比率意味着，服务器k的服务率是μk（i），当协作的分量Pj为导数Pj，ij，即当其底层马尔可夫过程处于状态ij或节点j处的队长为ij时，1≤j≤M。一个主动动作的反向动作的每一次出现，比如说，在Ak是常数净到达率λk的常数分数，因为每个分量都是M/M/1队列 因此，满足WMARCAT的条件1，我们得到= 1−P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6171下面是针对代理Pj，0（j = 1，. ，M）：xij=p ij.λi+CIMMk=1Σx个聚气（i = 1，.（男）(We对于xaij，使用缩写xij，1≤i/ =j≤M。）现在让vi=λiCIMMk=1 x个聚气对于1≤i≤M，使得：xij=vipij1≤i，j≤M这些是内部流的传输方程，其中xij是从节点i到节点j的内部传输速率。因此，解总是存在于不可约网络中。事实上，对i求和，我们得到vj−λj=CIMMi=1vip ij这是网络的通常的流量或WMARCAT的第二个条件很简单，因为在正向和反向过程中的每个状态下都启用了所有被动操作。对于第三个条件，与极小圈有关，我们必须检查由每对分量过程形成每个组件表示一个M/M/1排队，因此只有一个形式为i−1→i→i− 1的极小圈，其中i≥1。因此，只有两个（参数化的）基本循环，形式为：逆时针：（i-1，j- 1）→（i，j-1）→（i，j）→（i-1，j）→（i-1，j- 1）和C：（i−1，j− 1）→（i−1，j）→（i，j）→（i，j−1）→（i−1，j− 1）其中i，j≥1是各个组件过程中的状态此外，由于M/M/1队列的反向过程是相同的M/M/1队列（易于检查由于这个队列满足详细的平衡[14]），顺时针和逆时针正方形是彼此相反的循环。因此，证明围绕这两个平方的速率的乘积相等就足够了。现在，WMARCAT中由分量Rk表示的队列中的速率i-1→i是恒定传输速率vk如上定义-它不依赖于服务速率函数。因此，我们必须证明，对于由分量h和k导出的基本圈，1≤h/ =k≤n，vhvkμh（i）μk（ih）=vkvhμk（i）μh（ik）其中ik=（i1，.，ik−1，ik−1，ik+1，.，in）-ik：−1在先前的记法中。这简单地说，μk（ih）=μh（ik）（一）μk（i）μh（i）+72P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61v1v1KKKK对于1≤h/ =k≤n和有效状态i. 因此，满足这些方程的任何一组服务率函数也将验证WMARCAT的第三个条件本发明的逆转PEPA剂，1≤j，k≤M：Mdak=1LPk，0现在直接如下：Mdak=1LXk，0，其中，对于λkX=（e，μ（i））Xn >0k，n k vkkk，n−1X=（a，xjkμ（i））Xn >0k，nJKvkkΣk，n−1Xk，n=（dk，（1-j/=kpkj）vk）Xk，n+1n≥0Xk，n=（akj，T）Xk，n+1n≥0其中Lk={akj|j/= k}{ajk|jk}。反向操作的比率很容易使用近似规则计算-将费率分配给反向子操作;参见第2节。例如，考虑在节点1处的反向外部到达，其具有类型e1。节点1的总离开率为μ1（i），e1在前向过程中的比例为λ1。因此反作用e1的速率为λ1μ1。类似地，网络的平衡概率的可分离解这是一个非常一般的结果，但是如果存在合适的服务率函数，那么存在什么3.3.1依赖网络负载的服务器假设节点k的服务速率根据网络的全局状态和节点k的局部状态进行乘法修改。也就是说，μk（i）=g（i）μJ（ik）对于某些函数g和μj-g，对于所有分量节点是相同然后，等式1意味着，对于所有i，ih，ik>0，g（ih）=g（ik）。因此，反复应用这个等式会导致：g（i）= g（i1 + 1，i2−1，i3，.，in）=g（i1+ i2，0，i3，. ，in）= g（i1 + i2+…+ in，0，.、0）的它是网络总人口的函数，我们将其表示为g（i1 + i2 +.. +in）。应用WMARCAT，我们得到以下平衡存在时的可分离状态概率：命题3.8一个具有常数到达率和状态依赖服务率的稳态马尔可夫网络，在节点k=克伦克1、...，M，其中N =k=1ik是网络人口，具有均衡概率nπ（i）k=1.vik/ikj=1ΣμJ（j）NjP.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6173=1 g（j）74P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61KK证据 应用WMARCAT，我们发现⎛ ⎞π（i）Mk=1乌克兰Ikj=1g（i1 +.. +ik−1+j）μJ（j）结果如下。Q3.3.2Coxian队列众所周知，一个具有全局资源共享的共享磁盘的节点样条线在包含该节点的网络中的平衡概率的乘积形式解中贡献了可分离因子。 这一因素由上一节的结果，g（i）=1/MI. 然而，K已知功能服务速率依赖性可以是当前网络人口的任何函数，而不仅仅是反比。例如，随着人口的增加，速率可能下降得不那么快，例如与其平方成roo t orrlogarithm，orrperhapsin.creaselinarlyrquaratrically，orrrexotically，由g（i）= sinCIMMk =1 ik。一个S相Coxian随机变量通常被认为是S≥1个指数时滞的有限序列的截断和。s延迟后截断的概率是a1a2. as−1（1 −as），其中aS= 0。 因此，具有处理器的路由节点共享（PS）的维护规则和S阶段的Coxian服务时间可以模拟作为S个节点的标准串联杰克逊网络，其中在节点s处服务后离开网络的概率为1−as， 1≤s≤S。所有客户同时获得服务的速度与数量成反比在Coxian节点，即与S节点杰克逊网络中的号码相任何数量的客户可以在同一时间在每个阶段，因为没有阻塞的客户。在阶段s，每个客户以速率μs/（i1+ i 2）接收服务。. + iS），给出了在该阶段的服务速率函数isμs/（i1+. +iS）。然而，对全局状态的依赖可以是Coxian节点数量的任何函数，而不仅仅是反比，给出服务率函数isμsg（i1 +. +iS），对于所选择的函数g。通过这种方法，我们得到了Coxian条件节点：λNS .一 ...一卢塞恩岛π（i）1k−1i1！... 是S！Nj=1 g（j）μik=1其中N = i1 +. +iS.在常规PS规程的特殊情况下，这变成N！N！λNS .a.. . 阿努伊π（i）1k−1i1！... 是S！ k=1 μi公司简介对i求和，...，i使得i = N，则产生均衡队列1Sk=1k长度概率（通过多项式定理的常规应用）π（N）πρNk=1P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6175k=1K其中ρ=λ/μ，μ−1=λSa1. ak−1-1是平均服务时间， 的Coxian服务器。我们现在可以应用定理3.7来获得乘积形式，参见。文[1]中给出了一个具有FCFS排队规则和指数服务时间或GPS排队规则和Coxian服务时间的排队网络。Coxian服务时间的后到先服务（LCFS）规则也可以包含在RCAT框架中，如[10]所述，也可以包含在类似于PS的有限服务器（IS）中。在每种情况下，在正向和反向合作的每种状态下，所有被动动作都被启用，所需的反向速率xa由传输方程给出，因此可以应用WMARCAT，给出已知的乘积形式。扩展到多类的情况也很简单，如[10]中所讨论的4结论弱多代理反向复合代理定理（WMARCAT）大大简化了其前身RCAT的使用，用于任意数量代理的合作更重要的是，允许同步动作的速率（即功能速率）中的全局状态依赖性这一结果的主要应用是一个新的，机械化的推导多类BCMP定理的网络与PS服务器的队列，推广到更广泛的一类排队网络与子网络的全局状态依赖服务器。据作者所知，还发现了新的可分离解该方法可以自动化，其新的通用，多代理形式促进了许多不同的可分离解决方案的统一推导，如[9，10]中仅考虑两个组件的合作这些应用的范围从多类网络到G网络的众多变体，再到在关键部分具有互斥和阻塞的网络。引用[1] F. Baskett，K. M.钱迪河R. Muntz和F. Palacios，Open，Closed and Mixed Networks of Enterpriseswith Di Different Classes of Customers，J. ACM，22（2）：248-260，1975.[2] M.贝尔纳多湖Donatiello和R. Gorrieri。将并发系统的性能和功能分析与EMPA集成，Proc。第一届分布式系统研讨会：算法，架构和语言，pp。5-6，Levico（意大利），1996年6月。[3] R.J. Boucherie竞争马尔可夫链的独立性特征及其在随机Petri网中的应用。IEEE软件工程学报，20（7）：536[4] X. Chao，M. Miyazawa和M. Pinedo. 嵌入式网络：客户，信号和产品形式的解决方案。Wiley，1999年[5] E. Gelenbe，G网络的第一个十年，欧洲运筹学杂志，126（2）：231-232，2000年10月。[6] William J. Gordon 和 Gordon F. Newell ， Closed Exclusive Systems with Exponential Servers ，Operations Research，15（2）：254-265，Mar-Apr 1967。μ76P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）61[7] 彼得·哈里森。马尔可夫过程代数中的回溯时间理论计算机科学，290（3）：1947-1986，2003年1月。[8] 彼得·哈里森。基于马尔可夫过程代数的G-网络机械解In Proc. International Conference on StochasticModelling and the IV International Workshop on Retrial Approaches ， Cochin ， India ， December2002，Notable Publications，2002.[9] P.G. 哈里森合成反向马尔可夫过程及其在G-网络中的应用《绩效评估》，2004年出版。[10] Peter G.哈里森逆向过程、产品形态和一些非产品形态。J.线性代数应用，出现，2004年。[11]H. Hermanns，M. Rettelbach和T.伟.具有不确定分支的集对分析中即时行为的形式化描述。计算机杂志，38（7）：530-541，1995年。[12] 简·希尔斯顿。一种性能建模的合成方法。博士论文，爱丁堡大学，1994年。[13] J. R. Jackson. 类似于车间的装配系统。Management Science，10（1）：131-142，1963.[14] 弗兰克·P凯利逆向和随机网络。John Wiley Sons Ltd，1979年。附录A：基于PEPA的MPA我们使用马尔可夫过程代数语言来定义代理，代理表示连续时间马尔可夫链。代理通过执行具有指数分布持续时间的动作而进化一个动作是一个对，第一个组成部分是它的类型（或名称），第二个组成部分是它的速率。因此，MPA规范中的代理和动作分别对应于底层马尔可夫过程中的状态和转换。MPA在比显式状态转换图更高的层次上描述系统。特别是，PEPA的合作组合子精确地定义了代理如何以简洁的方式交互，使用对其动作速率的通用描述。原始PEPA语言的精确语义在[12]中给出，并定义了由PEPA代理表示的马尔可夫过程请注意，术语然而，这些术语本质上是同构的。在本文中，我们只使用MPA PEPA的前缀和合作组合子（在本文的主体中直接推广到多个合作）：(i) 前缀组合子定义了一个agent（a，λ）.P，它以速率λ执行类型（或“名称”）a的动作（a，λ）(ii) 描述两个代理P和Q的合作的代理，这两个代理在特定集合L中的类型上同步动作，写作PDQ。L在本文所考虑的合作中，L中的每一种行动类型都是主动的，即具有特定的实值速率，在代理人P，Q中恰好有一个，而在另一个中是被动的，即合作中的联合行动的速率就是为主动行动所规定的速率。被动动作由未指定的速率指示表示为T，基本上是无限的，在这个意义上，行动将立即一旦其同步动作准备好。 类型为L的任何操作只能继续同时在两个合作的代理人。 马尔可夫过程表示P.G. Harrison/Electronic Notes in Theoretical Computer Science 151（2006）6177i，i+1JIJ由合作有一个状态空间与两个维度，分别对应于每个组成部分的合作;有关WMARCAT（定理3.7在第3.2节）其中n≥2个组件协作，状态空间具有n维，类似地对应于每个组件。新的代理人被定义使用分配组合子，A=P，和rela-beling，P{y←x}，表示过程P，其中所有的占领的符号y被改变为x，这可能是一个表达式。 例如，（（a，λ）.P）{λ←μ}表示agent（a，μ）.P{λ←μ}. 选择是通过对过程名称，而不是传统PEPA的单独组合符符号+反向实体（代理、动作、动作类型、动作速率）用上条表示。附录B：反向过程一个随机过程它的关键性质是，一个阶段的反向马尔可夫过程，具有状态空间S、生成矩阵Q和平稳概率π的平稳马尔可夫过程{Xt}具有生成矩阵QJ，定义为：J= πjqji/πi（i，j∈ S）和相同的平稳概率π。这个结果是标准的，例如见[14]，并立即产生π的乘积形式的解决方案.这是因为，在不可约马尔可夫过程中，我们可以任意选择一个参考状态0，找到一个连接状态序列，正向或反向过程，0，. ，j（即，其中qi，i+1> 0或qJ>0为0≤i≤j− 1），并计算j−1qj−1qJπj=π0i=0时i，i+1=π0i+1，ii=0时i，i+1qi+1，iQQ