分布式计算-GHS算法选举算法

1、GHS算法只需要局部知识就能得到最优消息复杂度。

2、

1）保持片断集合，满足所有片断的并集包括所有节点。

2）初始时，集合中包含的每个节点是由一个节点组成的片断。

3）通过片断中节点找出片断的最小带权出边。

4）当已知片断的最小带权出边时，通过增加出边，将片断之间连接过来。

5）当只剩一个片断时，算法终止。

3、

1）片断名：每个片断中的进程有相同的名字，通过比较片断名，进程就知道一条边属于内部边还是出边。

2）大小片断的组合：当组合2个片断时，将较小者组合进较大者中，用较大片断名作为新片断名。

3）片断级：每个片断有一个级，用于相互比较的依据。

当片断F1与更高一级的片断F2组合后，新片断F1∪F2的级与F2相同。

2个同级片断的组合形成一个新的片断，级别比当前被组合的片断高一级，片断的新名字为组合2个片断的边上的权值,这条边称为新片断的核心边。核心边所连接的2个节点称为核心节点。

4、组合策略概述。

规则A：如果eF通向L <L'的片断F'=（FN’，L‘），F组合成F’，新片断名为FN‘，片断级为L’，这些新值被发送到F中所有进程中。

规则B：如果eF通向L=L'的片断F‘=(FN',L')，且eF'=eF，这2个片断组合成新片断，片断级为L+1，片断名为w(eF)，这些新值被发送到F和F‘中所有进程中。

规则C：在所有其他情况下，片断F必须等待直到规则A或规则B被应用。

5、每个信道pq 的状态stachp[q]，状态是分支的，如果得知它是MST中一条边；该状态是reject(废弃的)，如果它是MST中的一条边；该状态是basic(基本的)，如果这条边仍未用。对于片断P，fatherp是通向片断中核心边的边。

6、

var statep   :(sleep,find,found)

      stachp[q]  :(basic,brach,reject) for each∈Neighp

      namep,bestwtp     :real;

      levelp          :integer;

      testchp,bestchp,fatherp  :Neighp;

      recp:integer;

 

(1)As the first  action of each process,the algorithm must be initialized:

begin let pq be the channel of p with smallest weight;

          stachp[q]:=brach;levelp:=0;

           statep:=found;recp:=0;

           send <connect,0> to q

end

 

(2)Upon receipt of <connect,L> from q:

begin if L<levepp then (*规则A*)

           begin stachp[q]:=brach;

                     send <initiate,levelp,namep,statep> to q

          end

    else if stachp[q]=basic

                then  (*规则C*) process the message later

                else  (*规则B*) send <initiate,levelp+1,w(pq),find> to q

end

 

(3)Upon receipt of <initatie,L,F,S> from q:

     begin levelp:=L;namep:=F;statep:=S;fatherp:=q;

               bestchp:=udef;bestwtp:=∞; 

               forall r∈Neighp:stachp[r]=branch∧r≠q do

                         send <initiate,L,F,S> to r;

               if statep=find then begin recp:=0;test end

   end

 

(4)procedure test:(*寻找出边，即寻找通过另一个片断的边*)

begin if q∈Neighp;stachp[q]=basic then

             begin testchp:=q with stachp[q]=basic and w(pq) minimal;

                       send <test,levelp,namep> to testchp

            end

        else begin testchp:=udef;report end

end

 

(5)upon receipt of <test,L,F> from q:

 begin if L>levelp then

               process the message later

           else if F=namep then (*内部边*)

                      begin if statchp[q]=basic then stachp[q]:=reject;

                               if q≠testchp

                                   then send <reject> to q

                                   else test

                       end

                   else send <accept> to q

end

 

(6)upon receipt of <accept> from q:

       begin testchp:=udef;

                   if w(pq)<bestwtp

                            then begin bestwtp:=w(pq);bestchp:=q end;

                        report

     end

 

(7)upon receipt of <reject> from q:

begin if stachp[q]=basic then stachp[q]:=reject;

           test

end

 

(8)procedure report:

begin if recp=#{q:stachp[q]=branch∧q≠fatherp}

               and testchp=udef then

           begin statep:=found;send <report,bestwtp> to fatherp end

end

 

(9)upon receipt of <report,w> from q:

begin if q≠fatherp

          then

                  begin if w<bestwtp then

                              begin bestwtp:=w;bestchp:=q end;

                            recp:=recp+1;report

                 end

          else(*pq是核心边*)

                 if statep=find

                      then process this message later

                 else if w>bestwtp

                            then changeroot

                            else if w=bestwtp=∞ then stop

  end

 

(10)procedure changeroot:

       begin if stachp[bestchp]=branch

                 then send <changeroot> to bestchp

                 else begin send <connect,levelp> to bestchp;

                                  stachp[bestchp]:=branch

                        end

        end

 

(11)upon receipt of <changeroot>:

      begin changeroot end

 

7、

1）<connect,L>是连接两个被组合的片断形成新片断的边传递的消息。是由片断级小的进程发送给片断级大的进程。如果2个片断级一样，则互相交换

2）<initiate,...>消息用于把新片断的消息在新片断内扩散。

3）<report....>消息用于向每个子树报告这条最小带权出边。

4）当核心节点的2条消息<reportt,w>相遇时，核心节点知道最小带权出边（通向片断外的边）的权值。如果在该点上根本没有出边报告，则算法终止。如果报告一条出边，从报告最好边的核心节点开始，沿着每个节点中的bestch指针找到最好的边。消息<connect,L>必须通过这条边发送，片断中所有father指针必须指向这个方向，可以通过发送出消息<changeroot>完成。当<changeroot>到达依附最小带权出边的节点时，这个节点通过最小带权出这发送消息<connect,L>进行新一轮的片断组合