What Is Bully Algorithm In Mutual Exclusion

Mutual Exclusion is when any process wants to read or update certain shared data structures, and it has to first enter into the critical section to achieve the mutual exclusion, that ensures that no more than one process can enter into the critical section and can use that shared data structure at the same time. 

To achieve mutual exclusion, you can have it from many solution such as – Semaphores, local variables, and monitors. Though Mutual exclusion is a simple task for a standalone system, it can get very complex when it deals with Distributed environments.

Some of the reasons fot its complexity are -

• DS  not having any shared memory
• Information Propagation delay
• Synchronization issue with the clocks
• There is no ordering of events, suggested by Lamport.

There are several algorithms to achieve critical section and mutual exclusion in DS, some of them are -

• Centralized Algorithm
• Distributed Algorithm
• Token Ring Algorithm.

In Distributed environments, there is a need of a permanent or temporary leader- commonly called Coordinator, which carries out specific tasks and also it controls the whole system, which relates to mutual exclusion.

There might be the chance of node crash, link failure or any other calamity, which hinders the algorithm, as we are dealing with networking. At that time, it's probable that the Coordinator will crash too. In such cases, there is a need to elect a new leader or a coordinator to control the system.

These election algorithms have two major goals as -

• They find the process with the highest process number and allocate him as a Coordinator. It also informs all other active processes about this newly elected Coordinator.

• The second major aspect of this algorithm is to allow the crashed Coordinator to again start a fresh new election and establish the control. There are more chances that the failed Coordinator wins again, as it is having a highest process number in the processes.

There are two Election algorithms given below.

• Bully Algorithm
• Ring Algorithm

Here, in this article, we will discuss more about the Bully algorithm and in the next phase, we will understand what Ring algorithm is

Bully Algorithm

This algorithm has three main components given below.

• Coordinator – Announce about himself.
• Election – Announces the election.
• Reply – Acknowledge the request.

Let’s say the scenario is, we have 6 process numbered as 1, 2, 3, 4, 5, 6 and also, the priority or process number are also in the same order, therefore the process 6 is the highest process number. The process are shown below; Circles are the processes and the square boxes are their numbers.

Now, suppose the case is Process 6 has crashed and other processes are active. The crashing has been noticed by process 2. It finds out that the Process 6 is longer responding to the request. In this case, Process 2 will start a fresh election.

Process 2 sends an election message to the process, which has the highest number. In our case, the processes are 3, 4, 5, 6. Now, as Process 6 is down or fails, it will definitely not respond to the election message.

Process 3, 4, 5 are active and therefore they respond with a reply or acknowledgement message to Process 2.

If no one will respond to the request message by Process 2, it will win the election. Now, the election will be initiated by the next highest number. In our case, it is Process 3, which will send the election message to Process 4, 5 and 6. As Process 6 is down, it will again not respond to the request message. Again, if no one will respond, then Process 3 will win the election.

It will be the same process  for Process 4 and it will be the next initiator to conduct the election. Now, the chance came to Process 5, as it is the highest in all processes. Also, because Process 6 is down. In this case, Process 5 will win the election and will send this victory message to all.

Meanwhile, Process 6 came back from the down state to active state. It will definitely hold the election, as it is the highest among the processes in the system. It will win the election, which is based on the highest number and control over the Coordinator job.

Whenever the highest number process is recovered from the down state, it holds the election and win the election. Also, it bullies the other process to get in submission.

The complexity of this algorithm is given below.

• Best Case - n-2
• Worst Case - 0(n^2)

Hope you like it. Have a good day. Thank you for reading.