Nickyhw

          研究Java技術,算法設計以及移動開發

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
            2 隨筆 :: 0 文章 :: 0 評論 :: 0 Trackbacks

          Danny Dolev等在1982年提及了一種未改進的extreme-find算法,該算法過程簡要描述如下:

          算法中使用的消息類型有兩種:

          M1:形式為<1,i>;

          M2:形式為<2,i>。

          其中,i表示存儲在進程中的一個數字。每個進程v都含有一個變量max(v),當該進程是激活(active)狀態時,該變量可以用來存儲位于當前進程左邊的另一個激活的進程的變量。

          被動的(passive)進程僅僅是簡單的傳遞它們接收到的消息。對于算法的描述,我們可以僅僅對其中一個進程的行為進行描述就可以了。

          算法     A0. 發送消息<1,max(v)>.

          A1. 如果接收到一條消息<1,i>,則執行以下操作:

          1. 如果imax(v)則發送消息<2,i>,并且將i復制給left(v)。

          2. 否則,終止——max(v)是全局最大值。

          A2. 如果接受到一條消息<2,i>,則執行以下操作:

          1. 如果left(v)大于j和max(v)則將left(v)賦值給max(v),然后發送消息<1,    max(v)>

          2. 否則,變為被動進程。

              基于以上的算法描述,我們可以利用Spin建模語言Promela對其進行建模如下:

           1 mtype = { one, two, winner };
           2 chan q[N] = [L] of { mtype, byte};
           3 
           4 proctype node (chan inoutbyte mynumber)
           5 {    bit Active = 1, know_winner = 0;
           6      byte nr, maximum = mynumber, neighbourR;
           7 
           8     xr in;
           9     xs out;
          10 
          11     printf("MSC: %d\n", mynumber);
          12     out!one(mynumber);
          13 end:    do
          14     :: in?one(nr) ->
          15         if
          16         :: Active -> 
          17             if
          18             :: nr != maximum ->
          19                 out!two(nr);
          20                 neighbourR = nr
          21             :: else ->
          22                 know_winner = 1;
          23                 out!winner,nr;
          24             fi
          25         :: else ->
          26             out!one(nr)
          27         fi
          28 
          29     :: in?two(nr) ->
          30         if
          31         :: Active -> 
          32             if
          33             :: neighbourR > nr && neighbourR > maximum ->
          34                 maximum = neighbourR;
          35                 out!one(neighbourR)
          36             :: else ->
          37                 Active = 0
          38             fi
          39         :: else ->
          40             out!two(nr)
          41         fi
          42     :: in?winner,nr ->
          43         if
          44         :: nr != mynumber ->
          45             printf("MSC: LOST\n");
          46         :: else ->
          47             printf("MSC: LEADER\n");
          48             nr_leaders++;
          49             assert(nr_leaders == 1)
          50         fi;
          51         if
          52         :: know_winner
          53         :: else -> out!winner,nr
          54         fi;
          55         break
          56     od
          57 }
              該模型描述了每個進程節點的行為,通過該算法,可以找出網絡中的領導者。算法的計算復雜度為2nlogn+O(n) 。
          posted on 2012-06-27 00:47 Nickyhw 閱讀(629) 評論(0)  編輯  收藏

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 临夏县| 永德县| 宜兰县| 郯城县| 鹤壁市| 图木舒克市| 禄劝| 同德县| 古田县| 兴义市| 新民市| 商洛市| 呼和浩特市| 临洮县| 满洲里市| 潮安县| 察雅县| 广南县| 枣强县| 监利县| 揭阳市| 繁昌县| 高平市| 门头沟区| 河北省| 金塔县| 垫江县| 陆川县| 逊克县| 师宗县| 新化县| 抚松县| 思南县| 遂昌县| 中西区| 六安市| 德格县| 灌南县| 万安县| 汶川县| 峨边|