Return to Contents


Distributed Algorithms


 

 


Election Algorithms

Election Algorithms

-a group of processes on different machines need to choose a coordinator

            -peer to peer communication: every process can send messages to every other process.

            -Assume that processes have unique IDs, such that one is highest

            -Assume that the priority of process Pi is i

(a) Bully Algorithm

Background: any process Pi sends a message to the current coordinator; if no response in T time units, Pi tries to elect itself as leader. Details follow:

 

Algorithm for process Pi that detected the lack of coordinator

  1. Process Pi sends an “Election” message to every process with higher priority.
  2. If no other process responds, process Pi starts the coordinator code running and sends a message to all processes with lower priorities saying “Elected Pi
  3. Else, Pi waits for T’ time units to hear from the new coordinator, and if there is no response à start from step (1) again.

 

Algorithm for other processes (also called Pi)

            If Pi is not the coordinator then Pi may receive either of these messages from Pj

           

            if Pi sends “Elected Pj”; [this message is only received if  i < j]

 

                        Pi updates its records to say that Pj is the coordinator.

            Else if Pj sends “election” message (i > j)

                        Pi sends a response to Pj saying it is alive

                        Pi starts an election.

 

(b) Election In A Ring => Ring Algorithm.

-assume that processes form a ring: each process only sends messages to the next process in the ring

- Active list: its info on all active processes, including itself

- assumption: message continues around the ring even if a process along the way has crashed.

 

 

Background: any process Pi sends a message to the current coordinator; if no response in T time units, Pi initiates an election

  1. initialize active list to empty.
  2. Send an “Elect(i)” message to the right and add i to active list.

 

If a process receives an “Elect(j)” message

            (a) this is the first message sent or seen

                        initialize its active list to [i,j]; send “Elect(i)” + send “Elect(j)”

            (b) if (i != j), add i to active list + forward “Elect(j)” message to the next process

            (c) otherwise (i = j), so process i has complete set of active processes in its active list.

                        => choose highest process ID + send “Elected (x)” message to neighbor

If a process receives “Elected(x)” message,

            set coordinator to x

           

Example:

 

Suppose that we have four processes arranged in a ring:  P1 à P2 à P3 à P4 à P1 …

P4 is coordinator

Suppose P1 + P4 crash

Suppose P2 detects that coordinator P4 is not responding

P2 sets its active list to [ ]

P2 sends “Elect(2)” message to P3; P2 sets active list to [2]

P3 receives “Elect(2)”

This message is the first message seen, so P3 sets its active list to [2,3]

P3 sends “Elect(3)” towards P4 and then sends “Elect(2)” towards P4

The messages pass P4 +  P1 and then reach P2

P2 adds 3 to its active list [2,3]

P2 forwards “Elect(3)” to P3

P2 receives the “Elect(2) message

            P2 chooses P3 as the highest process in its list [2, 3] and sends an “Elected(P3)” message
P3 receives the “Elect(3)” message

            P3 chooses P3 as the highest process in its list [2, 3] and then sends an “Elected(P3)” message

Note: The last two messages can be processed in either order and the result will be the same.

 

Byzantine Generals Problem

           

Intuition: Only want to proceed with the plan of attack if they are sure everyone else agrees

Can't trust other generals.

-If generals can't trust one another they can never be sure if they should attack.

 

 


Return to Contents