---
title: "Bully algorithm vs ring algorithm"
subject: "Distributed System"
chapter: 6
key: "semester_7/distributed_system:election-bully-ring"
source: https://www.bctengineer.com/q/semester_7/distributed_system/election-bully-ring
site: BCT Engineering
---

# Bully algorithm vs ring algorithm

Distributed System · Chapter 6: Coordination and Agreement

- Asked in: 2071 Chaitra, 8 marks
- Video: [Bully Algorithm vs Ring Algorithm | Election Algorithms in Distributed Systems (Cloud Computing)](https://www.youtube.com/watch?v=NT0qU3-EDa0) — Vaibhav Vhargar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/election-bully-ring
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6

## Question

Write the importance of election algorithm. Explain BULLY algorithm with suitable example. Compare it with Ring based algorithm.

## Short answer

Election algorithms automatically choose a new coordinator when the current one fails, ensuring fault tolerance. In Bully, a process detecting failure sends ELECTION to higher ids; the highest alive wins and broadcasts COORDINATOR (e.g., if 6 crashes, 5 becomes coordinator). Compared to Ring, Bully uses O(N²) messages in worst case while Ring uses 2N; Bully is faster for high-id initiators but relies on timeouts and complete topology knowledge.

## Answer

#### Importance of election algorithms
Many distributed algorithms need one process to act as coordinator, server, token generator or master (centralised mutual exclusion, Berkeley time daemon, primary replica). When it crashes, the remaining processes must choose a new one that everyone agrees on. An election algorithm selects exactly one process, usually the one with the highest id, without human help. It provides fault tolerance and availability.

#### Bully algorithm
Assumptions: each process has a unique id, knows the ids of all others, the system is synchronous with timeouts, and reliable messages. The process with the **highest id wins** (the "bully").
1. A process P that notices the coordinator is not responding starts an election: it sends ELECTION to all processes with higher ids.
2. If no one answers within the timeout, P wins: it sends COORDINATOR to all other processes.
3. If a higher process Q answers (OK), P stops; Q takes over and holds its own election among higher processes.
4. Finally the highest alive process wins and announces COORDINATOR to all. When a crashed process recovers, it starts an election and takes over if it has the highest id.

Example: processes 1 to 6, coordinator 6 crashes. P3 notices and sends ELECTION to 4, 5, 6. 4 and 5 reply OK. 4 sends ELECTION to 5 and 6; 5 sends ELECTION to 6. 6 does not answer; 5 gets no OK from higher, so 5 broadcasts COORDINATOR(5).

#### Ring algorithm
Processes form a logical ring; no token is used. A process that notices failure sends ELECTION(its id) to its successor (skipping dead ones). Each receiver appends its own id and forwards. When the message returns to the initiator, it picks the highest id in the list and circulates a COORDINATOR message with this id.

#### Comparison
| Point | Bully | Ring |
|---|---|---|
| Topology | Fully connected, all ids known | Logical ring, only successor known |
| Messages (worst) | O(N²) | 2N (N election + N coordinator) |
| Best case | N−2 messages | Same, 2N |
| Winner | Highest alive id | Highest id in the ring list |
| Who starts | Any, highest wins in the end | Initiator circulates list |
| Failure handling | Timeouts | Skip failed successors |
| Speed | Faster when the initiator is high | Slow: full ring traversal |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Why are election algorithms needed?
   A. When the coordinator fails, the rest must automatically agree on exactly one replacement
   B. To create a token for mutual exclusion only
   C. To synchronise physical clocks
   D. To encrypt messages
   Answer: A. Many algorithms depend on a coordinator; election provides fault tolerance and availability. (Key point: Importance of election)

2. In the bully algorithm, a process P detects coordinator failure. What does it do first?
   A. Sends ELECTION to all with lower ids
   B. Sends ELECTION to all processes with higher ids
   C. Sends ELECTION to its ring successor only
   D. Declares itself coordinator at once
   Answer: B. Only higher-id processes can beat P, so it contacts them; no OK means it wins. (Key point: Bully step)

3. In the example (1-6, 6 crashed, P3 starts), why does 5 become coordinator?
   A. 5 has the lowest id
   B. 3 is chosen by majority
   C. 5 sends ELECTION to 6, gets no OK, and so announces COORDINATOR(5)
   D. 6 reappears and defers to it
   Answer: C. The highest live id gets no answer from higher processes and broadcasts itself. (Key point: Bully example)

4. Which comparison of worst-case messages is correct?
   A. Bully 2N; Ring O(N^2)
   B. Both O(N^2)
   C. Both about N-2
   D. Bully O(N^2); Ring about 2N
   Answer: D. Bully may have many processes starting elections; the ring uses N election plus N coordinator messages. (Key point: Message complexity)

## Related in Distributed System

- [When Bully and Ring algorithms suit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Abully-ring-suitability) — Distributed System, chapter 6
- [Need of consensus; Bully algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aconsensus-bully) — Distributed System, chapter 6
- [Election algorithm need and example](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-scenario) — Distributed System, chapter 6, asked 2×
- [Centralized vs Ricart-Agrawala algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acentral-vs-ra-compare) — Distributed System, chapter 6
- [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×
- [Central coordinator election; consensus](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-central-consensus) — Distributed System, chapter 6

## Related in other subjects

- [GA vs fuzzy based learning](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aga-vs-fuzzy-learning) — Artificial Intelligence, chapter 6
- [DSB-AM vs SSB; ring modulator for DSB-SC](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Adsbam-ssb-compare-ring-modulator) — Communication Systems, chapter 2
- [SSB vs full carrier AM; ring modulator](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Assb-vs-am-ring-modulator) — Communication Systems, chapter 2
- [Slip ring vs squirrel cage induction motor](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machines_i%3Aslip-ring-vs-squirrel-cage) — Electrical Machines I, chapter 5