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 阅读(604) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: