Create a distributed algorithm for leader election in a cluster.
- User
Create a distributed algorithm for leader election in a cluster.
- Assistant
Distributed Leader Election Algorithm: Bully Algorithm
Overview
The Bully Algorithm is a classic distributed algorithm for leader election in a cluster of nodes. It elects the node with the highest unique ID as the leader, ensuring progress in the presence of crash failures. It's simple, requires no shared memory or central coordinator, and works over asynchronous message passing.
Key Properties
- Correctness: The highest-ID alive node is always elected.
- Termination: Eventually completes if no new failures during election.
- Fault Tolerance: Handles crash-stop failures (nodes fail silently and permanently).
- Communication: O(N²) messages in worst case (fully connected network).
System Model
- Nodes: N processes (nodes) with unique IDs from 1 to N (higher ID = higher priority).
- Network: Asynchronous, reliable message delivery (no losses/duplicates), fully connected (unicast messages).
- Failures: Crash-stop (nodes may crash but don't recover or send spurious messages).
- Triggers: Election starts when a node detects no leader (e.g., heartbeat timeout, startup, or leader failure notification).
- Messages:
Type From → To Purpose ELECTIONCandidate → Higher IDs Announce candidacy OKHigher → Candidate Acknowledge (I'm alive/higher) COORDINATOR(id)Winner → All Declare leader
Algorithm Steps
Node States
FOLLOWER: Default, following current leader.CANDIDATE: Running for election.LEADER: Elected, sends heartbeats.
Pseudocode
Each node maintains:
myID: Unique ID.leaderID: Current known leader (-1 if none).timeout: Heartbeat timer.
Events and Handlers
1. ON STARTUP or HEARTBEAT_TIMEOUT (no leader detected): become CANDIDATE send ELECTION(myID) to all nodes with ID > myID start election_timer (to detect no replies) 2. ON RECEIVE ELECTION(senderID) from lower ID: if I'm alive: send OK to senderID become CANDIDATE // Bully back! send ELECTION(myID) to all nodes with ID > myID start election_timer 3. ON RECEIVE OK from a node: // Collect OKs from all higher IDs if OKs received from ALL higher IDs (or timer expires with no responses): become LEADER send COORDINATOR(myID) to ALL nodes cancel election_timer start heartbeat_timer (periodic heartbeats to followers) 4. ON RECEIVE COORDINATOR(leaderID): set leaderID = leaderID become FOLLOWER reset heartbeat_timer 5. ON HEARTBEAT from leader: reset heartbeat_timer // Stay FOLLOWERDetailed Flow Example (4 nodes: IDs 1,2,3,4)
- Node 1 detects no leader → Sends
ELECTION(1)to 2,3,4. - Node 2 receives → Sends
OKto 1, sendsELECTION(2)to 3,4. - Node 3 receives from 2 → Sends
OKto 2, sendsELECTION(3)to 4. - Node 4 receives from 3 → Sends
OKto 3. (No higher → Timer expires → SendsCOORDINATOR(4)to all.) - Nodes 1,2,3 receive
COORDINATOR(4)→ Elect 4 as leader.
If node 4 crashes mid-election:
- Node 3's timer expires (no OK from 4) → Sends
COORDINATOR(3).
Handling Edge Cases
- New Node Joins: On join, check for leader via heartbeat. If none, initiate election.
- Leader Crashes: Followers timeout → Initiate election (only highest alive wins).
- Multiple Simultaneous Elections: Highest ID "bullies" others into submission.
- Network Partitions: Not handled (requires consensus like Raft/Paxos for Byzantine faults).
- Optimizations:
- Use a ring topology for O(N) messages.
- Integrate with heartbeats to detect failures faster.
Implementation Notes
- In Code (e.g., Go/Python): Use UDP/TCP for messages, unique process IDs (UUID + timestamp), thread-safe state.
- Scalability: Poor for large N (O(N²)); use Raft/Zab for production (log-based, handles partitions).
- Testing: Simulate with tools like Jepsen or ns-3.
This algorithm is deterministic and easy to implement. For production clusters (e.g., Kubernetes etcd), prefer Raft for stronger guarantees.
If you need code snippets, variations (e.g., ring-based), or adaptations for specific tech (e.g., Kafka, Consul), let me know! 🕵️
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.