How the bully works
Each node has a unique id. The rule is simple: the highest id alive becomes leader. When a node notices the leader is gone, it starts an election:
- It sends an Election message to every node with a higher id.
- If none reply within a timeout, it declares itself leader and broadcasts a Coordinator message.
- If a higher node replies with OK, the starter steps back and that higher node takes over the election.
The name comes from larger ids bullying smaller ones out of contention.
Cost and assumptions
- Messages are O of n squared in the worst case when the lowest node starts.
- It assumes reliable delivery and reasonably synchronous timeouts to detect failure.
- Recovery is fast once messages settle because the answer is deterministic: the surviving maximum.
A node that recovers and has the highest id will simply start an election and reclaim leadership.
Key idea
The bully algorithm always elects the highest live id by having higher nodes override lower ones, at a cost of up to n squared messages.