java代写: LCR Algorithm

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

  1. 22:  upon receiving hinID; in; 1i from clockwise neighbour, in which inID 6= myIDi
  2. 23:  sendCounterclocki := hinID; in; 1i

24:

  1. 25:  upon receiving hinID; in; 1i from both clockwise and counterclockwise neighbours, in both of which inID = myIDi holds
  2. 26:  phasei := phasei + 1 phase
  3. 27:  sendClocki := hmyIDi; out; 2 i i
  4. 28:  sendCounterclocki := hmyIDi; out; 2phasei i

29:

  1. 30:  // The following to be always executed by all processors, i.e.,
  2. 31:  // also in round 1 in which no message has been received
  3. 32:  send sendClocki to clockwise neighbour
  4. 33:  send sendCounterclocki to counterclockwise neighbour