`
deepfuture
  • 浏览: 4321103 次
  • 性别: Icon_minigender_1
  • 来自: 湛江
博客专栏
073ec2a9-85b7-3ebf-a3bb-c6361e6c6f64
SQLite源码剖析
浏览量:79301
1591c4b8-62f1-3d3e-9551-25c77465da96
WIN32汇编语言学习应用...
浏览量:68099
F5390db6-59dd-338f-ba18-4e93943ff06a
神奇的perl
浏览量:101182
Dac44363-8a80-3836-99aa-f7b7780fa6e2
lucene等搜索引擎解析...
浏览量:280241
Ec49a563-4109-3c69-9c83-8f6d068ba113
深入lucene3.5源码...
浏览量:14534
9b99bfc2-19c2-3346-9100-7f8879c731ce
VB.NET并行与分布式编...
浏览量:65149
B1db2af3-06b3-35bb-ac08-59ff2d1324b4
silverlight 5...
浏览量:31183
4a56b548-ab3d-35af-a984-e0781d142c23
算法下午茶系列
浏览量:45067
社区版块
存档分类
最新评论

分散式基本计算-Shavit-Fracez检测终止性

阅读更多

当算法达到终止配置时,分布式算法的计算终止,即配置中不存在进一步可应用的算法步,每个进程处于允许接收的状态,且所有信道为空,即消息终止,则这个配置是终止的。

1、分散式基本计算是指在一个初始配置中,有多个活动进程。

1、算法将Dijkstra-Scholten算法推广,动态地维持图F=(VF,EF)

1)或者T为空,或者F是若干个以初始进程为根的有向树组成的森林。

2)集合VT包括 所有活动进程,以及传输中的所有基本消息。

图变空时,终止检测。

2、算法

var statep:(active,passive) init if p=p0 then active else passive;

       scp:integer init 0;

        fatherp:P init if p=p0 then p else udef;

        emptyp:boolean init if p is initiator then false else true;

Sp: {statep=active}

      begin send <mes,p>;scp:=scp+1 end

Rp:{A message <mes,q> has arrived at p}

      begin receive <mes,q>;statep:=active;

                if fatherp=udef then fatherp:=q else send <sig,q> toq

      end

Ip:{statep=active}

    begin statep:=passive;

              if scp=0 then

                    begin if fatherp=p

                                 then emptyp:=true

                                 else send <sig,fatherp> to fatherp;

                            fatherp=udef;

                     end

 

Ap:{<sig,p> arrivates at p}

     begin receive <sig,p>;scp=scp-1;

              if scp=0 and statep=passive then

                 begin if fatherp=p(*就是当前的树只有根节点P了*)

                             then emptyp:=true

                             else send <sig,fatherp> to fatherp;

                         fatherp:=udef

                end

     end

进程并发执行波动算法,其中,仅当emptyp为true时,p发送或判定,decide调用annouce

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics