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. 如果i≠max(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 in, out; byte 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) 。