1 Objectives
This assignment requires you to implement in Java two distributed
algorithms for leader election in a ring network.
2 Description of coursework
Throughout this coursework, the network on which our algorithms are to be executed is a bidirectional ring, as depicted in Figure 1.
u1 un
u n−1
u8
u2
u3
u4 u5
u7
u6
Figure 1: A bidirectional ring network on n processors.
In our setting, all processors execute the same algorithm, do not know the number n of processors in the system in advance, but they do know the structure of the network and are equipped with unique ids. The ids are not necessarily consecutive and for simplicity you can assume that they are chosen from f1; 2; : : : ; ng, where 1 is a small constant (e.g., for = 3, the n processors will be every time assigned unique ids from f1; 2; : : : ; 3n 1; 3ng). Additionally, every processor can distinguish its clockwise from its counterclockwise neighbour, so that, for example, it can choose to send to only one of them or to send a different message to each of them. Processors execute in synchronous rounds.
2.1 Implementing the LCR Algorithm|30% of the assignment mark
As a rst step, you are required to implement the LCR algorithm for leader election in a ring. The pseudocode of the non-terminating version of LCR can be found in Lecture 7 and is also given here for convenience (Algorithm 1).
Algorithm 1 LCR (non-terminating version) Code for processor ui, i 2 f1; 2; : : : ; ng:
Initially:
ui knows its own unique id stored in myIDi sendIDi := myIDi
statusi := \unknown”
1:
2: 3:
4: 5: 6:
7: 8: 9:
10: 11: 12: 13:
if round = 1 then
send hsendIDii to clockwise neighbour else// round > 1
upon receiving hinIDi from counterclockwise neighbour if inID > myIDi then
sendIDi := inID
send hsendIDii to clockwise neighbour else if inID = myIDi then
statusi := \leader ” else if inID < myIDi then
do nothing end if
end if
You are required to implement a terminating version of the LCR algorithm in which all processors eventually terminate and know the id of the elected leader.
2.2 Implementing the HS Algorithm|30% of the assignment mark
Next, you are required to implement another algorithm for leader election on a ring, known as the HS algorithm. As LCR, HS also elects the processor with the maximum id. The main di erence is that HS instead of trying to send ids all the way around in one direction (which is what LCR does), it has every processor trying to send its id in both directions some
distance away (e.g., k) and then has the ids turn around and come back to the originating processor. As long as a processor succeeds, it does so repeatedly (in \phases”) to successively greater distances (doubling the distance to be travelled each time, e.g., 2k). See Figure 2 for an illustration.
u n−1
u8
u2
u3
u4 id4
u7
u5
u1 un
u6
Figure 2: Trajectories of successive \phases” originating at processor u4 (imagine the rest of the processors doing something similar in parallel, but not depicted here). The id
transmitted by u4 aims to travel some distance out in both directions and then return back. If it succeeds, then u4 doubles the aimed distance and repeats.
Informally, each processor ui \operates in phases” l = 0; 1; : : : (where each phase l consists of one or more rounds). In each phase l, processor ui sends out a \token” (i.e., a message) containing its id idi in both directions. These are intended to travel distance 2l (that is, as in Figure 2, distance 20 = 1 for l = 0, distance 21 = 2 for l = 1, distance 22 = 4 for l
= 2, and so on) and then return to their origin. If both tokens manage to return back then ui goes to the next phase, otherwise it stops to produce its own tokens (and only performs from that point on the rest of the algorithm’s operations). A token is discarded if it ever meets a processor with greater id while travelling outwards (away from its origin). While travelling inwards (back to its origin), a token is forwarded by all processors without any check. The termination criterion is as follows: If a token travelling outwards meets its own
origin ui (meaning that this token managed to perform a complete turn of the whole ring
while travelling outwards), then ui elects itself as the leader. Observe that in order for tokens to know how far they should travel each time and in which direction, this information has to be included inside the transmitted messages (that is, apart from the id being transmitted,
the messages should also contain this auxiliary information).
The pseudocode of the non-terminating version of HS is given in Algorithm 2. As with LCR, you are required to implement a terminating version of the HS algorithm in which all processors eventually terminate and know the id of the elected leader.
Algorithm 2 HS (non-terminating version)
Messages are triples of the form hID; direction; hopCounti, where direction 2 fout; ing and hopCount positive integer.
Code for processor ui, i 2 f1; 2; : : : ; ng:
Initially:
ui knows its own unique id stored in myIDi
sendClocki containing a message to be forwarded clockwise or null, initially sendClocki := hmyIDi; out; 1i
sendCounterclocki containing a message to be forwarded counterclockwise or null, initially sendCounterclocki := hmyIDi; out; 1i
statusi 2 f\unknown”;\leader”g, initially statusi := \unknown”
phasei recording the current phase number, nonnegative integer, initially phasei = 0
1: 2:
3: 4:
5: 6: 7: 8: 9:
10: 11:
12: 13:
14: 15: 16: 17: 18:
19:
20: 21:
upon receiving hinID; out; hopCounti from counterclockwise neighbour if inID > myIDi and hopCount > 1 then
sendClocki := hinID; out; hopCount 1i elseifinID>myIDiandhopCount=1then
sendCounterclocki := hinID; in; 1i elseifinID=myIDithen
statusi := \leader” end if
upon receiving hinID; out; hopCounti from clockwise neighbour if inID > myIDi and hopCount > 1 then
sendCounterclocki := hinID; out; hopCount 1i elseifinID>myIDiandhopCount=1then
sendClocki := hinID; in; 1i elseifinID=myIDithen
statusi := \leader” end if
upon receiving hinID; in; 1i from counterclockwise neighbour, in which inID 6= myIDi sendClocki := hinID; in; 1i
- 22: upon receiving hinID; in; 1i from clockwise neighbour, in which inID 6= myIDi
- 23: sendCounterclocki := hinID; in; 1i
24:
- 25: upon receiving hinID; in; 1i from both clockwise and counterclockwise neighbours, in both of which inID = myIDi holds
- 26: phasei := phasei + 1 phase
- 27: sendClocki := hmyIDi; out; 2 i i
- 28: sendCounterclocki := hmyIDi; out; 2phasei i
29:
- 30: // The following to be always executed by all processors, i.e.,
- 31: // also in round 1 in which no message has been received
- 32: send sendClocki to clockwise neighbour
- 33: send sendCounterclocki to counterclockwise neighbour