Leader Election

Scenario: 3 database replicas
Problem: All 3 accept writes → Data diverges!

Solution: Elect 1 leader
- Leader accepts all writes
- Followers replicate from leader
- Consistent view of data

Initial state:
┌──────┐  ┌──────┐  ┌──────┐
│Node A│  │Node B│  │Node C│
│LEADER│  │follower│ │follower│
└──────┘  └──────┘  └──────┘

Network partition:
┌──────┐     │     ┌──────┐  ┌──────┐
│Node A│     │     │Node B│  │Node C│
│LEADER│     │     │follower│ │follower│
└──────┘     │     └──────┘  └──────┘
 Partition 1 │  Partition 2

Both sides elect leaders:
┌──────┐     │     ┌──────┐  ┌──────┐
│Node A│     │     │Node B│  │Node C│
│LEADER│     │     │LEADER│ │follower│
└──────┘     │     └──────┘  └──────┘

PROBLEM: Two leaders accepting writes!

3 nodes: Need 2 votes (quorum)
5 nodes: Need 3 votes (quorum)

Partition 1: Node A (1 vote) → Can't become leader
Partition 2: Nodes B, C (2 votes) → Can elect leader

Only one partition can have quorum!

class BullyElection:
    def __init__(self, node_id, all_nodes):
        self.node_id = node_id
        self.all_nodes = sorted(all_nodes)
        self.leader = None
        self.in_election = False
    
    def start_election(self):
        """Start election process"""
        print(f"Node {self.node_id}: Starting election")
        self.in_election = True
        
        # Find nodes with higher IDs
        higher_nodes = [n for n in self.all_nodes if n > self.node_id]
        
        if not higher_nodes:
            # I have highest ID - become leader
            self.become_leader()
            return
        
        # Send election messages to higher nodes
        responses = []
        for node in higher_nodes:
            response = self.send_election_message(node)
            if response:
                responses.append(response)
        
        if responses:
            # Higher node responded - wait for them to win
            print(f"Node {self.node_id}: Higher node responded, waiting...")
        else:
            # No response from higher nodes - I win!
            self.become_leader()
    
    def become_leader(self):
        """Declare self as leader"""
        self.leader = self.node_id
        self.in_election = False
        print(f"Node {self.node_id}: I AM THE LEADER!")
        
        # Announce to all lower nodes
        for node in self.all_nodes:
            if node < self.node_id:
                self.send_coordinator_message(node)
    
    def send_election_message(self, target_node):
        """Send election message to target node"""
        # Simulate message - returns True if node alive
        return is_node_alive(target_node)
    
    def send_coordinator_message(self, target_node):
        """Announce leadership to node"""
        # Notify node of new leader
        pass
    
    def receive_election_message(self, from_node):
        """Handle incoming election message"""
        if from_node < self.node_id:
            # I have higher ID - respond and start my own election
            print(f"Node {self.node_id}: Received election from {from_node}, bullying...")
            self.start_election()
            return True
        return False

# Example usage
nodes = [1, 2, 3, 4, 5]
node3 = BullyElection(node_id=3, all_nodes=nodes)

# Node 5 (leader) dies
# Node 3 notices and starts election
node3.start_election()
# Output: Node 3 becomes leader (highest alive ID)

┌──────────┐  timeout   ┌───────────┐  wins      ┌────────┐
│ Follower │───────────▶│ Candidate │───────────▶│ Leader │
└──────────┘            └───────────┘            └────────┘
     ▲                        │                       │
     │                        │ loses                 │
     │                        ▼                       │
     └────────────────────────────────────────────────┘

Phase 1: Prepare
- Proposer sends prepare(n) to acceptors
- Acceptors promise not to accept proposals < n

Phase 2: Accept
- Proposer sends accept(n, value)
- Acceptors accept if >= highest promise

3 nodes: Quorum = 2
5 nodes: Quorum = 3
7 nodes: Quorum = 4

Formula: Quorum = ⌊N/2⌋ + 1

5 nodes split into 2 partitions:
Partition A: 3 nodes  (has quorum) ✓
Partition B: 2 nodes  (no quorum)  ✗

Only Partition A can elect leader!

More nodes:
+ Higher availability (tolerate more failures)
- Slower consensus (need more votes)
- More expensive

Fewer nodes:
+ Faster consensus
+ Cheaper
- Lower availability

etcd uses Raft for leader election

3 or 5 voting members is common; odd counts use majority fault tolerance efficiently
Leader handles all writes
Followers replicate

If leader dies:
- Followers reach their configured election timeout
- New election starts
- Recovery time depends on timing and available quorum

ZooKeeper uses ZAB (ZooKeeper Atomic Broadcast)
Similar to Paxos/Raft

Used by:
- Older Kafka deployments used ZooKeeper; current Kafka uses KRaft
- HBase (master election)
- Hadoop (NameNode HA)

Uses Raft for consensus

Deploy 3 or 5 server nodes
Leader handles writes
Followers forward to leader
Used for service discovery + KV store

// Go client for etcd leader election
package main

import (
    "context"
    "fmt"
    "go.etcd.io/etcd/client/v3/concurrency"
    clientv3 "go.etcd.io/etcd/client/v3"
)

func main() {
    client, _ := clientv3.New(clientv3.Config{
        Endpoints: []string{"localhost:2379"},
    })
    defer client.Close()
    
    session, _ := concurrency.NewSession(client)
    defer session.Close()
    
    election := concurrency.NewElection(session, "/my-service/leader")
    
    // Campaign to become leader (blocks until elected)
    ctx := context.Background()
    if err := election.Campaign(ctx, "node-1"); err != nil {
        fmt.Println("Failed to campaign:", err)
        return
    }
    
    fmt.Println("I AM THE LEADER!")
    
    // Do leader work...
    doLeaderWork()
    
    // Resign leadership
    election.Resign(ctx)
}

func doLeaderWork() {
    // Only one node executes this at a time
    fmt.Println("Doing critical work as leader...")
}