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};
18 :: q[0]?two,_ -> break
22 :: q[0]?winner,_ -> break
26 proctype node (chan in, out; byte mynumber)
27 { bit Active = 1, know_winner = 0;
28 byte nr, maximum = mynumber, neighbourR;
33 printf("MSC: %d\n", mynumber);
44 /* Raynal p.39: max is greatest number */
57 :: neighbourR > nr && neighbourR > maximum ->
69 printf("MSC: LOST\n");
71 printf("MSC: LEADER\n");
73 assert(nr_leaders == 1)
77 :: else -> out!winner,nr
89 run node (q[proc-1], q[proc%N], (N+I-proc)%N+1);