没有合适的资源?快使用搜索试试~ 我知道了~
退化分布式随机协议的概率模型检验及其应用
理论计算机科学电子笔记250(2009)87-103www.elsevier.com/locate/entcs退化分布式随机协议道格拉斯·格雷厄姆,a Mu Zuy Caldera 和 爱丽丝·米勒aa英国格拉斯哥格拉斯哥大学计算科学系摘要我们提出了一种技术来解决一类特定的随机分布式系统,我们的马尔可夫决策过程模型的参数化概率模型检测问题。这些系统被称为退化系统,具有这样的性质:具有某种通信图的系统模型最终将表现得像具有简化图的系统模型。我们描述了一个归纳模式推理模型的退化系统在任意图形。因此,我们表明,一定类的定量LTL属性将持有任何通信图的系统的模型,如果它持有一些基础图的系统的所有模型。我们通过一个案例研究(a随机领导选举协议),使用PRISM建模语言指定。保留字:概率模型检验,参数化模型检验,退化系统,PRISM。1引言分布式系统的模型检查仅限于验证具有固定数量进程的系统证明一个具有N个相同过程的系统的一个性质,对于任何N >0,被称为参数化模型检查问题(PMCP)。这个问题通常是不可判定的[2],但可以使用技术来解决某些类型的系统。概率模型检测增强了传统的模型检测,使定量和定性分析。概率模型检测已经成为一个重要的研究领域,由于越来越多的概率算法的使用和分析的要求,不仅是系统的正确性,但也系统的per-perception。概率模型检查器,如PRISM [14],可以验证诸如“系统将以小于0.01的概率失败”和“概率为1,系统将终止”等属性概率模型检查工具在它们支持的基础模型我们专注于随机分布系统的概率模型检查,其模型表现出概率1571-0661 © 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2009.08.00788D. Graham等/理论计算机科学电子笔记250(2009)87→和非确定性的选择,因此,我们限制我们的注意力在MDPs推理。在本文中,我们通过扩展非概率参数化分布系统的归纳证明来解决随机分布系统的PMCP [16]。我们将这个证明推广到一类概率系统,描述为退化-生成该证明在系统的拓扑上使用归纳法,以表明对基本系统拓扑的模型成立的一类性质中的任何性质都将对任何大小和配置的系统的模型成立。归纳依赖于确定给定大小的系统的模型的任何行为等价于一个更小系统的模型。为了说明我们的技术,我们考虑使用PRISM指定的IEEE 1394 Firewire树识别协议[11]的2背景2.1马尔可夫决策过程其次,对于集合Y,Dist(Y)表示Y上所有离散概率分布的集合,即:所有函数sμ:Y→[0,1]的成立条件是y∈Yμ(y)=1.我们将随机分布系统建模为 马尔可夫 决策过程(MDP)。特别是,我们考虑状态标记的MDP,其中状态被增加了一组在该状态下为真的(原子)命题。定义2.1(例如,见[18])。 一个(标记的)马尔可夫决策过程是一个元组M=(S,s0,Steps,Act,L),其中S是一个有限的状态集,s0∈S是初始状态,Act是一个动作集,Steps:S→2Act× Dist(S)是概率转移函数,使得S∈S,Steps(s)/=S,L:S→2AP是一个命题集AP上的标记函数。对于MDP,M=(S,s0,Steps,Act,L),函数Steps将S中的每个状态映射到Act×Dist(S)的非空子集。直观地说,对于s∈S,Steps对|步骤|行动,分布对,选择行动a和分布μ,比方说。在S上进行概率选择,其中移动到状态sJ的概率由μ(sJ)给出。我们说a是由s使能的。如果对于某个状态sj,μ(SJ)> 0,我们说存在从s到SJ的跃迁,记为sa,μSJ。 行动a∈Act是非概率的i <$,<$s∈S,<$(a,μ)∈Steps(s),μ(sJ)= 1,对某些sJ∈S,并且是一个口吃动作i <$,<$s∈S,<$(a,μ)∈Steps(s),μ(sJ)>0=<$L(s)=L(sJ).无限路径,M中的α是非空序列sa0,μ00−→sa1,μ11−→... 其中对于i≥0,si∈S,(ai,μi)∈Steps(si),μ(si+1)>0. 同样,有限路径是一个非空的序列sa0,μ0sa1,μ1 ...an−1,μn−1s对于n≥0。 对于一个有限或无限0−→1−→−→n路径,α,|α|表示路径的长度(操作数)(|α|= ∞对于无限路径),和trAP(α)由状态的标签给出的序列在α中仅限于AP中的命题集合。对于有限路径,α=s0a0,μ0−→a1,μ1S1−→...an−1,μn−1−→sn,令last(α)= sn且P(α)= μ0(s1).μ1(s2).μn−1(sn)D. Graham等/理论计算机科学电子笔记250(2009)8789翅片翅片S翅片S翅片s0(withP(α)= 1,如果α=s0)。对于两条路径,α和αJ,如果α是αJ的前缀,我们写α≤αJ(如果它是严格前缀,则写α αJ从状态s开始的所有无限路径的集合由Path(s)给出,从s开始的所有有限路径的集合由路径翅片。2.2对手为了分析MDP,我们需要解决非决定论。这是通过考虑对手来完成的,对手是基于对状态s做出的选择的历史来对MDP的每个状态s的步骤(s)做出选择的构造。形式上,MDPM =(S,s0,Steps,Act,L)的对手A映射了M到集合Steps(last(α))的元素A(α)上[19]。一个对手产生一个有限状态马尔可夫链,每个状态由迄今为止所访问的状态的历史给出。一个敌手唯一地确定了这种形式的马尔可夫链,因此在下文中,当描述由MDP引起的马尔可夫链时,将方便地引用MDP的敌手。路径A(s)表示路径s的子集,A,同样,路径A(s),对应于A[19]的路径鳍对于路径α∈路径A(s),定义路径圆柱,C(α)={ω∈路径A(s)|α≤ ω}。概率测度,ProbA,定义在最小的σ-代数上,它包含所有集合C(α),对于所有α∈路径A (s),使得概率A(C(α))=P(α)(对于更多详细信息参见[13])。2.3削减定义2.2设M =(S,s0,Steps,Act,L)是一个MDP,设A∈AdvM。德费恩将(A)割为集合S. t的一族。 对于D∈Cut(A),D∈PathA(s0)其中,对于所有α∈D,α#αJanndαJ#α对于一个nyαJ∈D,αJ/=αanndα∈D概率A(C(α))=1。直觉,一个切割(一个边缘的简化,定义为概率平均,tomata由Segala [20])表示由对手引起的马尔可夫链的有限部分。给定MDP的对手A,对于n≥ 0,设割A(n)∈割(A)被定义为使得对于所有α∈割A(n),|α|= n.对于C∈Cut(A),我们说C是A的一个割。此外,我们将割A(n)描述为A在深度n处的割。2.4定量线性时间逻辑为了指定MDP的属性,我们采用线性时间逻辑(LTL)。LTL公式是根据MDP的路径定义的,并且具有形式语法φ::真正|一|¬φ1|φ1∧ φ2|φ1U φ2|X φ1其中a是一个原子命题,U和X是标准的until和next time操作符。 例如,[7]一个完整的说明. LTL\X被定义为LTL,但没有下一次操作符(排除该操作符并不是一个很大的困难,因为很少有人会考虑精确地为分布式算法中的下一个状态)。90D. Graham等/理论计算机科学电子笔记250(2009)87在MDP的状态上定义了一个数量LTL(QTL)公式,语法为φ::=PDap[n],其中Da∈ {≤,,>,≥},p∈[0, 1],n是LTL路径公式D. Graham等/理论计算机科学电子笔记250(2009)8791S00JJJJ0(对于QTL| X类似)。对于MDP,M,M的状态s,M的敌手A和LTL路公式,利用符号的滥用,我们令ProbA(α)=ProbA({α∈S s路径A|α |=})。对于QTL性质,φPDap [],s满足φ,记为s| = φ,i ∈ M,A∈AdvM,ProbA(n)Da p. M满足φ,(M| = φ)i s0|= φ其中s0是M的初始状态2.5口吃等价对于任何字符串v,应用于v的口吃消除运算符#将相同元素的每个最大有限子序列替换为该元素的单个副本设M和MJ分别是具有命题AP和APJ的 路径αM的称为口吃等价于MJ中的路径αJ(记为ααJ),其中关于APJAPAPJ当且仅当#trAP(γ)= #trAP(β)。 我们扩展通过考虑在原子命题集合序列上的跟踪圆柱体,来口吃对手的路径等价性。我们的定义基于[5]中给出的定义。定义2.3Let AP被 一 设置 的 提议的 跟踪圆柱C(1+,1+, . . ,1+)(对于10,11, . . . ,ln∈2个APpairiseditinct,n≥0)由0 1nC(1+,1+, . . ,l+)={t∈(2AP)ω)|t=1k0,1k1, . . . ,lkn, . . . 对于k0,k1, . . . ,kn≥1}0 1n0 1n其中,对于k≥ 1,lk= l,l,. . .,l∈ 2 AP.` 克雷奇对于初始状态为s0的MDPM的对手A,并且命题A P,通过在等式P A(C(1+,1+, . . ,l+))=ProbA({α∈P athA(s0)|trAP(α)∈C(l+,l+, . . ,1+)})。s00 1 n s00 1n定义2.4给定两个MDP,M=(S,s0,Steps,Act,L)和MJ=(SJ,sJ,StepsJ,ActJ,LJ),分别具有命题AP和APJ,两个对手A∈AdvM,AJ∈AdvMJ是概率口吃等价的(表示为AAJ)w. R.T.AP_J=AP_j = AP_ . ,1+))=AJ+s00 1 nAPJJ概率sJ(C(10,11,.,ln)),对于所有成对不相交的l0,l1,...,ln∈ 2,n≥ 0。为了方便,并与[5]保持一致,当我们显然是指对手之间的等价时,我们在下文中使用简写的口吃等价来表示概率口吃等价设S,T是集合,R<$S×T且μ∈Dist(S),ν∈Dist(T). μ和ν关于R的权重函数是函数w:S×T→[0, 1],使得w(s,t)>0∈ Rt,μ(s)=μt∈Tw(s,t),对于ys∈S和dν(t)=μs∈Sw(s,t),对于yt∈T.我们写μ±Rνi,其中存在μ和ν关于R的权函数。我们现在给出一对对手的条件,使我们能够在不考虑迹柱和只检查有限路径的情况下显示口吃等价性。引理2.5的证明在[20]中针对更一般的情况给出引理2.5令M=(S,s0,Steps,Act,L)和MJ=(SJ,SJ,StepsJ,ActJ,LJ)分别是具有命题集合AP和AP j的MDP。设APJJ<$AP<$APJ。92D. Graham等/理论计算机科学电子笔记250(2009)87x=0b 0.5x=1c10.51x=1c芬s000s0))=Probs(C({x=0}))=1,s0))=Probs(C({x=0},{x=1}))=10x=0ax=0b1J1MM图1.一、两个MDP,M和MJ,具有口吃等效对手设A和AJ分别是M和MJ的对手. 一如果存在切割,则为AJD0,D1,. 其中,i≥0Di∈Cut(AJ),使得(i) <$i≥0, <$α∈Di+1,α ∈Di或α=β,α,μ,s和β ∈Di,(ii) 对任意α∈路径A(s0),limi→∞β∈Di,α≤βP(β)=ProbA(C(α)),(iii) 对于每个i≥0,定义μi:cutA →[0,1],μJ:Di →[0,1],使得对于α∈cutA,我我αJ∈Di,μi(α)= P(α),μJ(αJ)= P(αJ). 则μi±RμJ,其中对于α∈割A,我我我αJ∈Di,R(α,αJ)i <$ααJw.r.t. APJJ.LTL\X属性导致了口吃不变的可测量语言[22],因此,通过测量理论的标准参数,可以得出以下结论:引理2.6如果M和MJ是分别具有命题AP和APJ以及副词A和AJ的MDP,则对于具有命题在APJ中,如果AJJJA AJ一个w.r.t. AP则Probs0(n)= ProbsJ(n)。例2.7在图1中,我们给出了MDP的一个例子,M和MJ,都是在集命题AP={x= 0,x = 1},初始状态为s0和sJ分别动作集合{a,b,c}和{b,c}。 只有一个对手对于每个MDP:设这些是A和AJ,则AAJw.r.t. 美联社自,ProbA(C({x=0}+一个J+J0ProbA(C({x=0}+,{x=1}+AJ++J0并且在所有其它跟踪圆柱上的概率度量为零。 如果是LTL\X属性,(trueUA AJM和MJ满足P≥1。(x = 1)),概率s0(x)=概率sJ(x)= 1。因此,在本发明中,2.6对手之间的同构同构对手必须具有完全相同的结构行为(直到状态标记定义2.8和引理2.9改编自[9]。定义2.8设M=(S,s0,Steps,Act,L)且MJ=(SJ,sJ,StepsJ,ActJ,LJ)为JA0AJJ分别与对手A和A的MDP设ρ:Pathfin(s0)→Pathfin(s0)是一个双射,其中ρ(s0)=SJ。 假设对所有α∈路径A,(s0),若A(α)=(a,μ)(a,μ)0J(aJ,μJ)J JJ翅片且ρ(α−→t)=α−→t则μ(t)=μ(t)for allt s. t. μ(t)>0。 那么,D. Graham等/理论计算机科学电子笔记250(2009)87930同构从A到AJ,并且A和AJ是同构的(记为A=AJ)。引理2.9令M=(S,s0,Steps,Act,L)和MJ=(SJ,sJ,StepsJ,ActJ,LJ)分别是具有命题AP和APJ的MDP,并且令m:AP→APJ是a94D. Graham等/理论计算机科学电子笔记250(2009)87芬0双射对于AP中的命题的LTL性质,()是通过将每个命题a替换为(a)而从得到的LTL公式。 设A是对手A(M的)与对手AJ(MJ的)之间的同构,使得对所有α∈路径A(s0),a∈AP,a∈L(last(α))<$(a)∈LJ(last(<$(α). 则对于任何LTL公式,A AJ对于来自AP的命题,Probs0()= ProbsJ(())。注意,在例2.7中,A和AJ不是同构的。2.7图我们定义一个图G=(E,V,I)为一个元组,其中V是顶点的集合,E是顶点对之间的边的集合,I是顶点的标号,每个顶点v ∈ V唯一地被值I(v)∈ {0,1,. 、|G|(1)其中|G|为|V|图的大小)。通过滥用符号,i表示顶点v,其中I(v)=i。 给定置换,{0,1,. 、|G|− 1},我们定义σ下的置换图为σ(G)=(E,V,IJ)其中IJ(v)= σ(I(v)),并将σ描述为G上的置换。对于一个图G =(E,V,I)且V J<$V,G [V J]=(EJ,V J,IJ)是由V j导出的子图,它是从G中删除V\V J中的顶点和相关边而得到的。3随机退化系统3.1通信图与约简在接下来的文章中,我们使用术语通信图来描述一个顶点标记的、非空的、有限的、简单的、连通的图(通过滥用符号,我们将通信图简单地称为图)。对于通信图G,我们引用顶点v,其中I(v)=i作为进程i,并将i描述为进程索引。 如果G有一条边(v,w),I(v)=i,I(w)=j,我们称进程i和进程j通信。一组通信图被定义为一个通信拓扑(或简称为拓扑)。非正式地说,如果一个系统最终表现为一个“更小”的系统,那么它就是退化的我们根据系统的拓扑形式化“较小”的概念定义3.1设Γ是拓扑,G=(E,V,I)∈Γ。设σ是G的一个置换,W<$V.则R=(W,σ)是G在Γ i中的约化,且R(G)=σ(G)[W]属于Γ.我们将R(G)描述为G在R下的在Γ中的约化通信图或简单地描述为G的约化通信图。例3.2考虑由图G、 G1和G2组成的拓扑Γ,如图2所示。这样定义集合W1和W2:W1={ 0, 1, 2, 3}和W2={ 0, 1, 2, 3, 4},并设置换σ1和σ2是单位置换和固定0和1,分别将3映射到2、4映射到3和5映射到4。则若R1=(W1,σ1),R2=(W2,σ2),则R1(G)=G1,R2(G)=G2. 因此R1和R2是G在Γ中的约化。D. Graham等/理论计算机科学电子笔记250(2009)8795Gi=0图二. 示例3.2的通信拓扑Γ定义3.3设Φ和Γ是拓扑,使得Φ ∈ Γ,且设QΓ={QG|G ∈Γ}是Γ中通信图的一族约简集,使得对所有G∈Φ,QG=Ω. 对于G∈Γ\Φ,存在一个约化序列R1,R2,.,Rn(对于某些n≥ 1),使得,对于所有1 ≤i≤n,Ri∈QRi−1(Ri−2(. (R1(G)和Rn(Rn−1(. (R1(G)). . ))∈Φ。3.2通信拓扑上的模型集我们考虑相对于某个变量集定义的MDP。对于通信图G,我们考虑G上的变量集,XG=<$N−1Xi <$G<$CG,其中,对于0≤i=0Gi≤N−1,每个Xi是与进程i相关联的一组局部变量。这些都是相同(直到索引)的每个过程。 集合GG是全局变量,Comm o ntoallprocess es. 这是一个可解的方程,CG={cj,k|j和dk_c_m_u_n_i_cat_e}用于在一对进程之间发送消息。对于x∈XG,D(x)表示x的定义域,D(XG)表示XG中各变量定义域的叉积.设对任意的c,CJ∈CG,D(c)=D(CJ). 我们将X G上的命题集定义为,APG={x = d|x∈XG,d∈ D(x)}.在续集中,我们区分索引和无索引的变量在XG。如果变量下标为进程索引(所有本地和通道),则变量被索引),或者如果它的域是进程索引的集合加上未签名的值,则为n(否则它是未索引的)。在第4节中描述的例子中,选择的变量是一个索引变量。在同一个例子中,一个本地变量-存储由给定进程接收到的最近消息的表MyMSG(比方说)将具有域{bmp,bmp,bmc,ack},并且因此将是未索引的。我们可以把这个定义推广到命题集合APGoverXG。 一个提议-位置x=d(x∈XG,d∈D(x))是有索引的,如果x是有索引的,而d是有索引的(否则它没有索引)。 如果LTL或QTL属性仅包含未索引的内容,则其为未索引的提议我们还假设对于MDP,在图G上有一组动作,ActG=<$N−1Acti,使得每个动作都是关于一个过程定义的,并且“局部”动作的集合定义3.4设G=(E,V,I)是通信图,XG是G上的变量集,ActG是G上的动作集.如果XG中变量的初始值由元组init(XG)给出,则G上的模型是MDP,MG=(D(XG),init(XG),StepsG,ActG,LG),使得LG用命题集合AP标记状态,其中AP在XG上定义。给定一个拓扑,设Mr={M G|G ∈ Γ}表示Γ上的一组模型。96D. Graham等/理论计算机科学电子笔记250(2009)870R( G)R( G)R( G)R( G)R( G)R( G)R( G)J3.3通信图置换诱导的映射给定图G和G的一个置换σ,设MG是G上的模型,Mσ(G)是σ(G)上的模型对于MG的对手A和Mσ(G)的对手AJ,我们定义了指数映射在由σ,ρ诱导的A上:路径A(sG)→路径AJ(sσ(G))映射过程指数fin0fin0与任何索引变量和任何动作相关联,根据σ。同样我们定义了变量集XG上的命题AP与Xσ(G)上的命题APJ之间由σ,φ诱导的命题指标映射.由于ρ尊重ρ,从引理2.9我们可以证明,对于AP中的命题的无索引LTL性质ρ,如果ρA AJ是同构,则Probs0(n)=ProbsJ (二)。3.4退化模型我们现在转向我们的主要定义,它给出了一个模型族(在拓扑上)退化的条件。关键的条件是拓扑的通信图被简化,使得在某个图上的模型的每个对手都是口吃等价于在简化图上的模型的对手定义3.5设Γ是在一族约化集下可约化为Φ的拓扑,QΓ={QG|G ∈ Γ}。 假设MΓ={M G|G ∈ Γ}是Γ上的一组模型。对于每个G ∈Γ,设XG是G上的一个变量集,APG是G上的G上的命题 对于每个R ∈QG,定义一组变量XJR(G)(与APJR(G),XJ上). Mr是退化性的其中基Φ在Qr(i) (约化变量与作用:)对G ∈Γ且R=(W,σ)∈QG,Xσ(G)\CG=XG\CG,D(Xσ(G))=D(XG),Actσ(G)=ActG,XR( G)<$Xσ( G),D( XR( G))<$D(Xσ( G)),Act R( G)<$Actσ( G),(ii) (匹配对手:)对G ∈Γ\Φ,存在R=(W,σ)∈QG,使得对于MG的每个对手A,存在Mσ(G)的一个对手AJ,它在σ诱导的指标映射下同构于A,且Aj是口吃的等价于MR(G)的某个对手AJJ关于APJ。通过退化的拓扑结构参数化的一组模型的建立提供了(在拓扑结构上的)归纳基础,利用该归纳基础来建立模型的属性。定理3.6设Γ是在约化集族Q Γ下可约化为Φ的拓扑,MΓ是Γ上的模型集。设对每个G ∈ Γ,R∈有一组变量XJXR(G)(与APJR(G)的集合XJ上的命题),使得MΓ在Q Γ下与基Φ退化。 然后对于任何未索引的QTL\X性质φ,G∈Γ\ΦR∈QG如果M F|= φ对于所有F∈ Φ,M G|= φ对所有G ∈ Γ。R(G),证据 设G ∈Γ,并假设φ是一个未索引的QTL\X属性,R∈QG中的位置JR(G)APAPD. Graham等/理论计算机科学电子笔记250(2009)8797. 假设M R(G)|=φ, 对每个R ∈QG. 我们可以证明M G|= φ,如下所示。 设A∈AdvMG. 选择R=(W,σ)∈QG使得A是98D. Graham等/理论计算机科学电子笔记250(2009)87R( G)sJJ000同构于某个AJ∈AdvMσ(G)在ρ下,σ诱导的A上的指数映射,其中AJ结巴等价于某个AJJ∈AdvMR( G)w.r.t. APJ. 特性φ其形式为PDap[]。 设Σ是由σ导出的命题指标图。 每MR(G)的敌手B,ProbB(G)Da p. 若M G,Mσ(G)和MR(G)有初态0s0,SJ和SJJ,那么,A AJJ概率s0()=第3.3节中的概率sJ=概率AJJ(),因为AJ一个JJW.R. T。APJ低于ρJJ0P在上面。R(G)由于上述情况对M G的每个对手都成立,M G|= φ。设φ是一个非指标QTL\X公式,其命题为G∈Γ R∈QGJR(G).设G然后, 由语句 的 定理,M G|= φ。 设G ∈Γ\ Φ。 φ在R∈QGJR(G)并且是未索引的,根据上述,M G|= φ if M R(G)|= φ对所有R∈QG. 对于每个R∈QG,或者R(G)∈Φ,或者可以进一步约化. 由于在QΓ下Γ可约化为Φ,继续这样,我们可以构造一棵图树,其中每个终端节点都是Φ中的图。最后,通过定理的陈述,与这些终端节点处的图相关联的每个模型都满足φ,并且通过向图的树上传播,可以得出M G|= φ。Q4IEEE 1394(Firewire)树识别协议的模型检验我们用一个案例研究来说明我们的技术。IEEE 1394(Firewire)树识别协议(TIP)[11]被设计为从以非循环拓扑结构排列的一组进程中选出领导者。 一个进程可以发送三种消息中的一种给相邻的进程:成为我的父进程(bmp),成为我的子进程(bmc)或者确认(ack)。任何从所有或除一个邻居外的所有邻居收到bmp消息的进程都用bmc消息响应,如果需要,向其余邻居发送bmp。相邻进程将在接收到bmc时发送ack,从这一点开始,进程在协议中不再起作用(因此协议是退化的)。以这种方式,协议建立一个生成树,根进程被选为领导者。两个相邻的进程可以通过同时向彼此发送bmp请求来尝试成为领导者。为了解决这个争用,每个进程在尝试再次发送请求之前,都如果一个进程在发送请求之前就收到了否则,必须重复另一个争用位置增强和“回退”过程。在证明TIP中根竞争的正确性方面已经做了很多工作[21]。呼吁这些结果,在早期的工作[6]中,我们建模的TIP与非确定性的竞争解决。在这里,我们考虑一类TIP的MDP模型,其中竞争是概率解决的我们用一个竞争过程来模拟竞争SAPAPD. Graham等/理论计算机科学电子笔记250(2009)87992G(conten,[i 2,.,ik,0,...,0],k,i 1,k)掷j=00.250.25(winner,[i 2,.,ik,0,...,0],k,i 1,k)掷j=1(失败者,[i 2,.,ik,0,...,0],k,i 1,k)掷j= 2图3.第三章。对应于进程j和i1(j i1)之间的争用解决的MG中的转换表1当进程j收到来自其所有邻居的请求时,它在MG中进行的转换1. 进程j接收bmp从所有的邻居。(s tart,[1] , . ..... . 你 好 。 ,k,k,0),[bmp]i,j,. . ,[bmp]ik,j1↓aj(child,[i1,i2, ...... . 你 好 。 ,ik,n, . . . ,n],k,n,k),[]i1,j, . . . ,[]ik,j2. 进程j响应向其邻国发出BMC请求。(child,[i1,i2, ...... . 你 好 。 ,ik,n, . . . ,n],k,n,k),[]i1,j, . . . ,[]ik,j1↓bj(p aren t,[i1,i2, . ..... . 你 好 。 ,ik,n, . . . ,k,k,k,k),[bmc]i1,j, . ..... . 你 好 。 ,[bmc]ik,j3. 进程j接收从所有的邻居中脱颖而出,成为领导者。(p aren t,[i1,i2, . . . ,ik,n, . . . ,k], k,k,k),[ack]i1,j, . ..... . 你 好 。 ,[ack]ik,j1↓cj(fi n is h,[m, . . . ,n],k,n,0),[]1,0, . . . ,[]N−1,0选择=j(the具有最小索引的一个)进行简单的概率选择:概率为1时,该进程失败并且另一进程发送其BMP;概率为1时,4 4该进程获胜并将其请求发送给另一个进程;或1争用未解决,进程必须重新选择。我们对TIP进行了建模,并使用PRISM验证了具有三个、四个和五个过程的所有系统配置的一套属性由于空间的原因,我们没有在这里给出我们的PRISM规格或我们所有的属性。我们集中我们在论文的其余部分都提到了一个属性。这里elected是一个全局变量(参见后面的部分),初始值为numb,并被设置为任何被选为leader的进程的索引值财产1. 一个领导人几乎肯定会被选举出来:P≥1 [真U <$(当选=)]。4.1非循环通信图使用TIP的小配置的PRISM规范作为基础,我们定义了用于自动生成TIP的PRISM规范对于任何拓扑结构。我们可以将此脚本视为指定TIP系统的一系列模型,MΓ={MG|G ∈Γ}在拓扑Γ上,是无圈的通信图的集合。给定G ∈ Γ,其中|G|=N,G上的模型M G有G上的变量集XG,其中,对于i∈ {0,.,N-1},GG={当选,掷0,掷1,. ,tossN−1},CG={cg,h,ch,g|(g,h)∈E},Xi={状态i,子i,0,子i,1,... ,child i,N−1,adj i,100D. Graham等/理论计算机科学电子笔记250(2009)87剩余伙伴i,请求i的数目},对于i,j ∈ {0,1,. ,N − 1},cg,h∈ CG,D. Graham等/理论计算机科学电子笔记250(2009)87101G表2当进程j收到除一个邻居(i1)以外的所有邻居的请求时,进程j在MG4. 进程j接收从除了i 1之外的所有邻居得到BMP。(s tart,[1] , . . . ,n],k,n,0),[]i1,j,[bmp]i2,j, . . . ,[bmp]ik,j1↓aj(ch ild,[i2, . . . ,ik,n, ...... . 你 好 。 ,n],k,i1,k),[]i1,j,[]i2,j, ...... . 你 好 。 ,[]ik,j....10. 进程j接收BMP来自I1并进入竞争。(r e spons e,[i2, . . . ,ik,n, . ..... . 你 好 。 ,k,i1,k),[bmp]i1,j1 ↓ej(conten,[i2,. 、.、 i k,n,. ......、n],k,i1,k),[] i1,j11. i1
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功