1 /* Dolev, Klawe & Rodeh for leader election in unidirectional ring
2 * `An O(n log n) unidirectional distributed algorithm for extrema
3 * finding in a circle,' J. of Algs, Vol 3. (1982), pp. 245-260
6 #define N 5 /* nr of processes (use 5 for demos) */
7 #define I 3 /* node given the smallest number */
8 #define L 10 /* size of buffer (>= 2*N) */
10 mtype = { one, two, winner };
11 chan q[N] = [L] of { mtype, byte};
15 proctype node (chan in, out; byte mynumber)
16 { bit Active = 1, know_winner = 0;
17 byte nr, maximum = mynumber, neighbourR;
22 printf("MSC: %d\n", mynumber);
33 /* Raynal p.39: max is greatest number */
46 :: neighbourR > nr && neighbourR > maximum ->
58 printf("MSC: LOST\n");
60 printf("MSC: LEADER\n");
62 assert(nr_leaders == 1)
66 :: else -> out!winner,nr
78 run node (q[proc-1], q[proc%N], (N+I-proc)%N+1);