- 2071 Chaitra · 8 marks
Bully algorithm vs ring 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.
Write the importance of election algorithm. Explain BULLY algorithm with suitable example. Compare it with Ring based algorithm.
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").
- A process P that notices the coordinator is not responding starts an election: it sends ELECTION to all processes with higher ids.
- If no one answers within the timeout, P wins: it sends COORDINATOR to all other processes.
- If a higher process Q answers (OK), P stops; Q takes over and holds its own election among higher processes.
- 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 |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- When Bully and Ring algorithms suit · Distributed System, chapter 6
- Need of consensus; Bully algorithm · Distributed System, chapter 6
- Election algorithm need and example · Distributed System, chapter 6 · asked 2×
- Centralized vs Ricart-Agrawala algorithm · Distributed System, chapter 6
- Token ring mutual exclusion · Distributed System, chapter 6 · asked 3×
- Central coordinator election; consensus · Distributed System, chapter 6
- GA vs fuzzy based learning · Artificial Intelligence, chapter 6
- DSB-AM vs SSB; ring modulator for DSB-SC · Communication Systems, chapter 2
- SSB vs full carrier AM; ring modulator · Communication Systems, chapter 2
- Slip ring vs squirrel cage induction motor · Electrical Machines I, chapter 5