Election Algorithm | Election Algorithm in Distributed System

Introduction:

An algorithm for choosing a unique process to play a particular role is called election algorithm. Election algorithms are designed to choose a coordinator. It is a special purpose algorithm, which is run for selecting the coordinator process among N number of processes.

Election algorithm chooses a process from a group of processes to act as a coordinator. If the coordinator process crashes due to some reasons, then a new coordinator is elected from other processes.

In general, election algorithms try to locate the process with the highest process number and designate it as coordinator. Every process knows the process number of every other process.

Requirement of Election Algorithm:

 

Many distributed algorithms require one process to act as coordinator, initiator, or otherwise perform some special role. The coordinator process plays an important role in the distributed system to maintain the consistency through synchronization.

Synchronization between processes often requires that one process acts as a coordinator. In those cases where the coordinator is not fixed, it is necessary that processes in a distributed computation decide on who is going to be that coordinator. Such a decision is taken by means of Election Algorithms. Election algorithms are primarily used in cases where the coordinator can crash. However, they can also be applied for the selection of superpeers in peer-to-peer systems.

Election algorithms are meant for electing a coordinator process from among the currently running processes in such a manner that at any instance of time there is a single coordinator for all processes in that system.

Election algorithm assumes that every active process in the system has a unique process number. The process with highest process number will be chosen as a new coordinator. Hence, when a coordinator fails, this algorithm elects that active process which has highest process number.

The goal of election algorithm is to choose and declare one and only process as the coordinator even if all processes participate in the election. And at the end of the election, all the processes should agree upon the new coordinator process without any confusion.

 

The Bully Algorithm:

The Bully Algorithm is a type of Election Algorithm. This algorithm was proposed by Garcia-Molina (1982). The idea behind the Bully Algorithm is to elect the highest-numbered process as the coordinator.

When any process notices that the coordinator is not active, crashed or no longer responding to requests, it initiates an election. A process, P, holds an election as follows:

1.  P sends an ELECTION message to all processes with higher numbers.

2.  If no one responds, P wins the election and becomes coordinator.

3.  If one of the higher-ups answers, it takes over. P's job is done or finish.

 

At any moment, a process can receive an ELECTION message from any one of its lower-numbered process. When such a message arrives, the receiver sends an OK message back to the sender to indicate that it is active and will take over. The receiver then holds an election, unless it is already holding one. Eventually, all processes give up but one, and that one is the new coordinator. It announces its victory by sending all processes a message telling them that starting immediately it is the new coordinator.

If a process that was previously down comes back up, it holds an election. If it happens to be the highest-numbered process currently running, it will win the election and take over the coordinator's job. Thus the biggest guy in town always wins, hence the name "Bully Algorithm."

Figure below shows an example of how the Bully Algorithm works:

The group consists of 8 processes, numbered from 0 to 7. Previously process 7 was the coordinator, but it has just crashed. Process 4 is the first one to notice this, so it sends ELECTION messages to all the processes higher than it, namely 5, 6, and 7 as shown in Fig-1.

            Fig-1

Processes 5 and 6 both respond with OK, as shown in Fig-2. Upon getting the responses, process 4 job is over. It knows that one of these will take over and become coordinator. It just sits back and waits to see who the winner will be.

        Fig-2

In Fig-3, both 5 and 6 hold elections, each one sending ELECTION messages to those processes higher than itself.

        Fig-3

In Fig-4 process 6 tells 5 that it will take over with an OK message. At this point 6 knows that 7 is dead and that it (6) is the winner.

    

        Fig-4

If there is state information to be collected from disk or elsewhere to pick up where the old coordinator left off, 6 must now do what is needed. When it is ready to take over, 6 announces this by sending a COORDINATOR message to all running processes shown in fig-5.

        Fig-5

When 4 gets this message, it can now continue with the operation it was trying to do when it discovered that 7 was dead, but using 6 as the coordinator this time. In this way the failure of 7 is handled and the work can continue.

If process 7 is ever restarted, it will just send all the others a COORDINATOR message and bully them into submission.


There are three types of messages that processes will exchange between each other during the Bully Algorithm:

1. ELECTION message

2. OK message

3. Coordinator message


An ELECTION message is sent to announce an election; an OK message is sent in response to an ELECTION message and a COORDINATOR message is sent to announce the identity of the elected process – the new ‘coordinator’.

 

The Ring Algorithm:

This algorithm is suitable for a collection of processes arranged in a logical ring. The Ring Election Algorithm is based on the ring topology with the process ordered logically and each process knows its successor in an unidirectional way, either clockwise or anticlockwise.

When any process notices that the coordinator process has crashed, it creates an ELECTION message, containing its own process number and sends the message to its successor. If the successor is down, the message would skip the successor and goes to the next process after its successor. On receiving an ELECTION message, a process adds its process number to the message before forwarding it to the next process in the ring.

Finally, the ELECTION message comes back to the process which initiated the message. Election initiator process analyses and finds the highest process number ( coordinator) among the available processes converts the ELECTION message into COORDINATOR message and removes all the process number from the list except the highest process number. This COORDINATOR message is circulated along the ring for one circulation to inform the running processes about who the new coordinator is. When this message is circulated once, it is discarded and the Election Algorithm ends here.

Figure below shows how the Ring Algorithm works:

Initially there are 8 process and all the processes are arranged in a logical ring.

Previously process 8 was the coordinator, but it has crashed. Process 2 and 5, discover simultaneously that the previous coordinator, process 8, has crashed. Each of these builds an ELECTION message and each of them starts circulating its message, independent of the other one.

Process 2 initiates an election

7 is the new coordinator elected by 2. Process 5 also detects coordinator has crashed, so 5 also initiates an election

Process 5 also understand that 7 is new coordinator because it has highest process number.

Process 2 and 5 converts ELECTION message to COORDINATOR message. All process recognized highest numbered process 7 as new coordinator.