Distributed Systems

Bully algorithm in distributed systems

0
(0)

What is Bully Algorithm

In distributed computing, the bully algorithm is a method for dynamically electing a coordinator or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator. This algorithm applies to system where every process can send a message to every other process in the system.

Bully Algorithm assumptions

  • system is synchronous.
  • processes may fail at any time, including during execution of the algorithm.
  • a process fails by stopping and returns from failure by restarting.
  • there is a failure detector which detects failed processes.
  • message delivery between processes is reliable.
  • each process knows its own process id and address, and that of every other process

How does Bully Algorithm work

  • Election Message: Sent to announce election.
  • Answer (Alive) Message: Responds to the Election message.
  • Coordinator (Victory) Message: Sent by winner of the election to announce victory.

When a process P recovers from failure, or the failure detector indicates that the current coordinator has failed, P performs the following actions:

  1. If P has the highest process ID, it sends a Victory message to all other processes and becomes the new Coordinator. Otherwise, P broadcasts an Election message to all other processes with higher process IDs than itself.
  2. If P receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.
  3. If P receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)
  4. If P receives an Election message from another process with a lower ID it sends an Answer message back and starts the election process at the beginning, by sending an Election message to higher-numbered processes.
  5. If P receives a Coordinator message, it treats the sender as the coordinator.

Network bandwidth utilization

Assuming that the bully algorithm messages are of a fixed (known, invariant) sizes, the most number of messages are exchanged in the group when the process with the lowest ID initiates an election. This process sends (N−1) Election messages, the next higher ID sends (N−2) messages, and so on resulting in  N*N messages.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments