Leader Election in Distributed Systems: Algorithms, Fencing Tokens, and Production Pitfalls

You have a background job that must run on exactly one node at a time. Or a cache-warming process where duplicate runs waste resources and cause consistency problems. Or a primary database replica that handles writes while the others stay read-only. In all three cases, you need the same primitive: a way for a group of processes to agree on which one is currently “in charge,” handle the failure of that process without human intervention, and do so correctly when networks partition or clocks drift.

This is leader election. It sounds simple until you try to implement it correctly, and then it reveals every hard problem in distributed systems simultaneously: split-brain, stale leaders, and the gap between “I believe I am leader” and “I actually am leader.”

The Core Problem

Leader election must satisfy three properties to be useful:

Safety (at most one leader): At any given time, at most one node believes it is the active leader and acts on that belief. Violating safety gives you split-brain: two nodes both writing to the same resource, both scheduling the same job, both believing they hold the same lock.

Liveness (at least one leader eventually): When the current leader fails, a new leader is elected within a bounded time. A system that elects no leader is safe but useless.

Correctness after partition: When a network partition heals, the system recovers to a single leader, and any node that was isolated during the partition stops acting as leader before rejoining.

Safety and liveness are in tension. Stronger safety guarantees (requiring strict quorum before acting) increase the time it takes to elect a leader after a failure. Most real systems accept a brief gap in leadership as a better tradeoff than two concurrent leaders.

Algorithm Comparison

Three broad approaches, each with different tradeoff profiles.

Consensus-Based Election (Raft-Style)

Raft uses leader election as a first-class primitive. Each node tracks a monotonically increasing term number. When a follower times out waiting for a heartbeat from the current leader, it increments its term, votes for itself, and sends RequestVote RPCs to other nodes. A node wins election if it receives votes from a majority quorum. A won election means strictly more than half of nodes agreed, so two nodes cannot simultaneously win an election in the same term.

The key properties:

• Safety via quorum: Majority overlap guarantees at most one winner per term.
• Log completeness constraint: A candidate can only receive votes if its log is at least as up-to-date as the voter’s log. This prevents a stale node from becoming leader and overwriting committed state.
• Term-based fencing built-in: Any message from an old term is rejected. A previously partitioned node that rejoins and tries to act as leader is immediately corrected.

Raft-style election is the right choice when you need a replicated state machine, which means you need leadership and replication to be coordinated. The complexity is significant. You are not just picking a leader; you are managing a replicated log.

Bully Algorithm

Simpler. Each node has a unique numeric ID. When a node detects the leader has failed (via missed heartbeat or direct connection failure), it initiates an election by sending an ELECTION message to all nodes with higher IDs. If any higher-ID node responds, the initiating node backs off and waits. The highest-ID node that responds declares itself leader and broadcasts a COORDINATOR message.

Properties:

• Simple to implement: The logic fits in a few dozen lines.
• Always elects the highest-ID available node: Deterministic outcome when the network is fully connected.
• Chatty under churn: Every node failure triggers a full election cycle with O(n²) messages in the worst case.
• No built-in safety under partition: If a partition isolates the highest-ID node, you may end up with two nodes simultaneously believing they are leader (one in each partition segment). The bully algorithm has no quorum requirement, so it cannot provide split-brain safety without additional mechanisms.

Bully is appropriate for small, stable clusters where network partitions are rare and the simplicity of the implementation matters more than theoretical safety guarantees.

Lease-Based Election

A node acquires a time-bounded lease from a coordination store. As long as it holds the lease and the lease has not expired, it acts as leader. It refreshes the lease before expiry. If it fails to refresh (process crash, network partition, slow GC pause), the lease expires and another node can acquire it.

Properties:

• Simple to understand: The semantics are close to a distributed mutex with TTL.
• Depends on clock synchronization: The correctness argument “the old leader’s lease expired before the new leader acquired one” requires that clocks are close enough that expired-on-the-store means expired-from-the-leader’s-perspective. Clock skew is the primary attack vector.
• Operationally flexible: Works with any key-value store that supports atomic TTL-based operations. Redis, etcd, and ZooKeeper all support this model.
• Does not prevent all overlapping leadership windows: A leader that experiences a 5-minute GC stop-the-world pause will still believe it is leader for those 5 minutes. Its lease will expire at the store level, another node will acquire leadership, and now both act as leader simultaneously. Fencing tokens are the solution.

Lease-based election is the most common approach in practice because it composes easily with existing infrastructure. The implementation below shows how to build it correctly with Redis.

Algorithm Comparison Table

Concern	Raft-Style Consensus	Bully Algorithm	Lease-Based
Split-brain safety	Strong (quorum required)	Weak (no quorum)	Weak without fencing tokens
Implementation complexity	High	Low	Medium
Infrastructure dependencies	Raft library or from-scratch	None	Coordination store (Redis, etcd)
Election time after failure	Seconds (election timeout)	Fast (seconds)	TTL-bounded (configurable)
Network partition behavior	Safe: minority partition gets no leader	Unsafe: both halves may elect	Unsafe: old leader may hold stale lease
Clock dependency	None	None	Yes (lease expiry)
Suitable cluster size	Any	Small clusters	Any with proper fencing

Lease-Based Leader Election in TypeScript

The following implementation uses Redis with the SET NX PX pattern for atomic lease acquisition. Every operation that requires leadership includes a fencing token (explained in the next section) to prevent stale leaders from causing damage.

import { createClient, RedisClientType } from "redis";
import { EventEmitter } from "events";
import { randomUUID } from "crypto";

interface LeaderElectionOptions {
  redis: RedisClientType;
  key: string;           // Redis key for the lease
  ttlMs: number;         // lease duration in milliseconds
  refreshIntervalMs: number; // how often to renew before expiry
  nodeId?: string;       // unique ID for this node, auto-generated if omitted
}

interface LeaseAcquisitionResult {
  acquired: boolean;
  fencingToken: number | null;
}

export class LeaderElection extends EventEmitter {
  private readonly redis: RedisClientType;
  private readonly key: string;
  private readonly ttlMs: number;
  private readonly refreshIntervalMs: number;
  private readonly nodeId: string;
  private readonly tokenKey: string;

  private isLeader = false;
  private refreshTimer: ReturnType<typeof setInterval> | null = null;
  private currentFencingToken: number | null = null;

  constructor(options: LeaderElectionOptions) {
    super();
    this.redis = options.redis;
    this.key = options.key;
    this.ttlMs = options.ttlMs;
    this.refreshIntervalMs = options.refreshIntervalMs;
    this.nodeId = options.nodeId ?? randomUUID();
    this.tokenKey = `${options.key}:token`;
  }

  async tryAcquire(): Promise<LeaseAcquisitionResult> {
    // Increment the fencing token counter and acquire the lease atomically
    // using a Lua script. The script ensures no other node can slip in
    // between the INCR and the SET.
    const script = `
      local token = redis.call('INCR', KEYS[2])
      local result = redis.call('SET', KEYS[1], ARGV[1] .. ':' .. token, 'NX', 'PX', ARGV[2])
      if result then
        return token
      else
        return false
      end
    `;

    const result = await this.redis.eval(script, {
      keys: [this.key, this.tokenKey],
      arguments: [this.nodeId, String(this.ttlMs)],
    });

    if (result === false || result === null) {
      return { acquired: false, fencingToken: null };
    }

    const fencingToken = Number(result);
    this.isLeader = true;
    this.currentFencingToken = fencingToken;
    this.startRefreshLoop();
    this.emit("elected", { nodeId: this.nodeId, fencingToken });
    return { acquired: true, fencingToken };
  }

  async refresh(): Promise<boolean> {
    if (!this.isLeader) return false;

    // Only refresh if we still own the lease (value matches our node ID + token)
    const script = `
      local current = redis.call('GET', KEYS[1])
      local expected = ARGV[1] .. ':' .. ARGV[2]
      if current == expected then
        redis.call('PEXPIRE', KEYS[1], ARGV[3])
        return 1
      else
        return 0
      end
    `;

    const result = await this.redis.eval(script, {
      keys: [this.key],
      arguments: [
        this.nodeId,
        String(this.currentFencingToken),
        String(this.ttlMs),
      ],
    });

    if (result !== 1) {
      // Lease was taken by another node. We are no longer leader.
      this.onLeadershipLost();
      return false;
    }

    return true;
  }

  async release(): Promise<void> {
    if (!this.isLeader) return;

    const script = `
      local current = redis.call('GET', KEYS[1])
      local expected = ARGV[1] .. ':' .. ARGV[2]
      if current == expected then
        redis.call('DEL', KEYS[1])
        return 1
      else
        return 0
      end
    `;

    await this.redis.eval(script, {
      keys: [this.key],
      arguments: [this.nodeId, String(this.currentFencingToken)],
    });

    this.onLeadershipLost();
  }

  private startRefreshLoop(): void {
    this.stopRefreshLoop();
    this.refreshTimer = setInterval(async () => {
      try {
        const stillLeader = await this.refresh();
        if (!stillLeader) {
          this.stopRefreshLoop();
        }
      } catch (err) {
        // Refresh failed due to Redis connectivity issue.
        // Conservatively give up leadership rather than risk split-brain.
        this.onLeadershipLost();
      }
    }, this.refreshIntervalMs);
  }

  private stopRefreshLoop(): void {
    if (this.refreshTimer !== null) {
      clearInterval(this.refreshTimer);
      this.refreshTimer = null;
    }
  }

  private onLeadershipLost(): void {
    const wasLeader = this.isLeader;
    this.isLeader = false;
    this.currentFencingToken = null;
    this.stopRefreshLoop();
    if (wasLeader) {
      this.emit("lost", { nodeId: this.nodeId });
    }
  }

  getStatus(): { isLeader: boolean; fencingToken: number | null; nodeId: string } {
    return {
      isLeader: this.isLeader,
      fencingToken: this.currentFencingToken,
      nodeId: this.nodeId,
    };
  }
}

Usage pattern:

const redis = createClient({ url: process.env.REDIS_URL });
await redis.connect();

const election = new LeaderElection({
  redis,
  key: "my-service:leader",
  ttlMs: 15_000,            // 15-second lease
  refreshIntervalMs: 5_000, // refresh every 5 seconds
});

election.on("elected", ({ fencingToken }) => {
  console.log(`Elected leader with fencing token ${fencingToken}`);
  startLeaderWork(fencingToken);
});

election.on("lost", () => {
  console.log("Lost leadership, stopping leader work");
  stopLeaderWork();
});

// Retry acquisition on a loop so followers elect themselves when the
// current leader releases the lease or its TTL expires.
async function participateInElection(): Promise<void> {
  while (true) {
    const { acquired } = await election.tryAcquire();
    if (!acquired) {
      // Back off before retrying to avoid thundering herd
      await new Promise((resolve) =>
        setTimeout(resolve, 1_000 + Math.random() * 2_000)
      );
    } else {
      break;
    }
  }
}

participateInElection();

Fencing Tokens

The most important correctness mechanism in lease-based election is the fencing token: a monotonically increasing integer that gets incremented every time leadership changes hands.

Consider what happens without it. A leader node running on a JVM experiences a full garbage collection pause of 20 seconds. Its 10-second lease expires at the Redis store. A new node acquires the lease and starts acting as leader. The GC pause ends. The original node does not know its lease has expired. It resumes acting as leader. For a window, both nodes believe they are leader.

A fencing token breaks this. Every write operation a leader performs against a shared resource includes its fencing token. The resource (a database, a file lock service, any storage system) records the highest fencing token it has seen and rejects operations with a lower or equal token. When the old leader (with token 42) resumes after its GC pause, the resource has already accepted writes from the new leader (with token 43). The old leader’s writes are rejected, not silently accepted.

// On the storage side: reject writes from stale leaders
async function writeWithFencingGuard(
  store: StorageClient,
  fencingToken: number,
  data: unknown
): Promise<void> {
  const highWatermark = await store.getFencingHighWatermark();

  if (fencingToken <= highWatermark) {
    throw new Error(
      `Stale leader write rejected: token ${fencingToken} <= watermark ${highWatermark}`
    );
  }

  await store.atomicWrite({ data, fencingToken });
}

The storage layer must be able to enforce the token check atomically. If the check and write are separate operations, a race condition can let two writes through. Most databases support this with conditional writes or compare-and-swap semantics.

Note: fencing tokens require cooperation from every system the leader writes to. If you have a leader that writes to a database, sends messages to a queue, and updates a cache, all three systems must enforce the token. A partial implementation is worse than no implementation, because it creates the false impression of correctness.

Split-Brain Scenarios

Split-brain is the state where two nodes simultaneously believe they are leader. Lease-based election is susceptible to it in several concrete ways.

Network partition to the coordination store. The leader loses connectivity to Redis. It cannot refresh its lease. The lease expires. Another node acquires it. The original leader is still running, still processing work, but no longer holds the lease. If it does not detect the connectivity loss and step down, it continues acting as leader while a new leader has been elected.

Mitigation: treat any failure to refresh the lease as an immediate loss of leadership. The implementation above does this: if refresh() throws for any reason, onLeadershipLost() is called. The cost is occasional false step-downs during brief Redis hiccups. The benefit is that a node never continues as leader with an expired lease.

Clock skew. The Redis server clock and the client clock diverge significantly. A lease set with PX 10000 expires 10 seconds from the server’s perspective. If the client’s clock is 30 seconds ahead, the client may believe the lease expired before it actually has, causing unnecessary elections. More dangerous is the reverse: a client whose clock is behind may believe its TTL is still valid while the server has already expired it.

Mitigation: use server-side time (Redis TIME command, or expiry evaluated by Lua scripts) rather than client-side time for expiry reasoning. The implementation’s Lua scripts run entirely on the Redis server, so client clock skew does not affect lease correctness.

GC pauses and process stalls. A long stop-the-world event (GC, OOM kill, container CPU throttling) stalls the leader’s refresh loop. The lease expires. A new leader is elected. The stall ends and the original node resumes.

Mitigation: fencing tokens, as described above. The original node’s writes are rejected by the storage layer because their token is stale.

“Brain” during leader handoff. When a leader deliberately releases the lease and a new leader acquires it, there is a brief window where no leader exists. Depending on your workload, this may be acceptable (background jobs) or require an explicit handoff protocol (zero-downtime primary replica switch).

Choosing the Right Approach

Scenario	Recommended Approach
Replicated state machine, consistent log required	Raft (use etcd, or a Raft library)
Small cluster (3-5 nodes), no partition tolerance needed	Bully algorithm
Single background job, occasional overlap is acceptable	Lease-based, no fencing tokens
Primary election with shared mutable state	Lease-based with fencing tokens
Cross-datacenter leader election	Raft with geo-distributed quorum
Kubernetes workload, one pod active at a time	Kubernetes lease API (built on etcd)

A few questions that sharpen the choice:

Can you tolerate brief split-brain windows? Background analytics jobs often can. Payment processing cannot. If overlap is catastrophic, you need either consensus-based election or lease-based election with strict fencing enforcement across all dependent stores.

How large is your cluster? Raft election performance degrades with cluster size. For very large clusters (50+ nodes), lease-based election with a single coordination store scales better because it does not require peer-to-peer voting.

Do you control the storage systems the leader writes to? If yes, you can add fencing token enforcement and get safety guarantees from lease-based election. If you use third-party systems that do not support conditional writes, fencing tokens become much harder to enforce consistently.

How important is fast failover? Raft-style elections can complete in 150-300ms when tuned aggressively. Lease-based failover is bounded by the TTL. A 15-second TTL means up to 15 seconds without a leader after a crash. For workloads that require near-instant failover, tune the TTL down (increasing the refresh rate and Redis load proportionally) or use Raft.

Production Considerations

Do not use the leader as the sole source of truth. Leadership state is ephemeral. Store the authoritative record of “what work the leader did” in a durable store, not in the leader’s in-memory state. If the leader crashes mid-task and a new leader takes over, the new leader should be able to reconstruct state from the durable record.

Test failover explicitly and regularly. Kill the leader process in a staging environment. Measure how long it takes for a new leader to be elected. Verify that the old leader’s in-flight operations were correctly rejected or rolled back. Most teams test the happy path (leader does work) but not the failure path (leader dies mid-operation).

Instrument every leadership transition. You want to know: which node is currently leader, how long it has held leadership, how many elections have occurred in the past hour, and whether any refresh failures happened. A spike in elections indicates instability in your cluster or Redis connectivity.

election.on("elected", ({ nodeId, fencingToken }) => {
  metrics.gauge("leader_election.is_leader", 1, { nodeId });
  metrics.increment("leader_election.elections_total", { nodeId });
  metrics.gauge("leader_election.fencing_token", fencingToken, { nodeId });
});

election.on("lost", ({ nodeId }) => {
  metrics.gauge("leader_election.is_leader", 0, { nodeId });
  metrics.increment("leader_election.leadership_lost_total", { nodeId });
});

Separate the election mechanism from the work. The LeaderElection class above only manages the lease. It does not know what work the leader should do. This separation means you can test the election logic independently, swap the coordination backend without changing your work logic, and make the “what the leader does” code ignorant of how it got elected.

Set TTL and refresh interval carefully. A common ratio is refreshIntervalMs = ttlMs / 3. This gives three refresh attempts before the lease expires, so two consecutive failures are survivable. At ttlMs = 15000 and refreshIntervalMs = 5000, you need three consecutive missed refreshes to lose the lease unintentionally, which covers most transient network blips.

Leader election is one of those problems where the implementation is straightforward but the reasoning about correctness is hard. A system that works under normal conditions may have subtle split-brain windows under partition or process stalls. Fencing tokens are the practical mechanism that makes the difference between “looks correct” and “correct under adversarial conditions.” Build in the tokens from the start. Retrofitting them later means touching every storage system the leader writes to.