Lease-Based Election

Imagine renting an apartment: you pay for exclusive access for a fixed period. When the lease expires, you must renew or vacate—the landlord can give the apartment to someone else. This simple, familiar concept revolutionizes leader election in distributed systems.

Lease-based election abandons the voting-based approaches of Bully and Ring in favor of time-bounded leadership grants. A leader doesn't win an election through message exchange with peers; instead, it acquires a time-limited lease from a coordination service. As long as the lease is valid, the holder is the rightful leader. When the lease expires—whether due to failure, partition, or intentional non-renewal—leadership becomes available for another node to claim.

This approach elegantly solves the split-brain problem that plagues traditional election algorithms. Even if a partitioned leader continues operating, its lease eventually expires, and it must stop acting as leader regardless of what it believes. Time becomes the ultimate arbiter of leadership validity.

A lease is a time-limited grant of exclusive access to a resource or role. In the context of leader election, the 'resource' is leadership itself. Let's formalize the properties of a lease:

Core lease properties:

1. Exclusivity: At most one holder at any time. If node A holds a valid lease, node B cannot hold a valid lease for the same resource.

2. Time-bounded: Every lease has an explicit expiration time. After expiration, the lease is no longer valid.

3. Renewable: Before expiration, the holder can request an extension. Successful renewal extends the lease; failure to renew means the lease expires.

4. Revocable (in some systems): The lessor (coordination service) can revoke a lease early, though this is less common for leader election.

5. Non-transferable: A lease cannot be passed from one holder to another. When leadership changes, the new leader acquires a fresh lease.

Lease-based systems make a critical assumption: clocks across the system are reasonably synchronized. This assumption deserves careful examination because violations can break safety guarantees.

The clock synchronization requirement:

When a lease server grants a 30-second lease, it expects:

1. Its clock and the client's clock agree on 'when 30 seconds pass'
2. The client will stop acting as leader before the server considers the lease expired
3. Any new leader will not start before the previous lease actually expires

If clocks drift significantly, these assumptions fail. Consider:

• Server grants lease at T=0, expires T=30
• Client's clock is 5 seconds slow
• Client thinks T=25 when server thinks T=30
• Server grants new lease to another client
• Old client still thinks it has 5 seconds left
• Split-brain: two clients believe they hold valid leases

Designing for clock uncertainty:

Practical lease systems build in safety margins to handle clock drift:

Guard period approach:

1. Lease duration: 30 seconds
2. Holder treats lease as valid for 25 seconds (5-second guard)
3. Even with 5 seconds of clock drift, holder stops before server considers lease expired

Example safety calculation:

Lease duration: 30 seconds
Maximum clock drift: 200ms/second (extremely conservative)
Maximum drift over lease: 6 seconds
Guard period: max_drift + network_latency = 6s + 1s = 7s
Effective leadership period: 30s - 7s = 23 seconds

The holder should stop acting as leader 7 seconds before lease expiration to guarantee safety even under maximum drift.

Implications:

• Longer leases → more effective leadership time → less overhead
• Shorter leases → faster failover → more renewal overhead
• More clock drift tolerance → larger guard periods → less effective time

Production systems typically use NTP for clock synchronization, achieving drift under 1 second in well-managed environments.

When a node wants to become the leader, it must acquire a lease. The acquisition protocol varies by implementation, but the core pattern is consistent across systems.

Basic acquisition flow:

Step 1: Check current lease state

• Query coordination service: 'Is there a current leader? Is the lease valid?'
• If valid lease exists for another node, acquisition fails
• If no valid lease exists, proceed to Step 2

Step 2: Attempt lease acquisition

• Send atomic acquisition request to coordination service
• Request contains: node ID, requested duration, current state (for compare-and-swap)
• If another node acquired simultaneously, exactly one wins (coordination service guarantees atomicity)

Step 3: Confirmation and activation

• If acquisition succeeds: receive lease with expiration time, begin acting as leader
• If acquisition fails: wait and retry (with backoff), or accept follower role

Step 4: Begin renewal cycle

• Before lease expires, request renewal (addressed in next section)

Implementation with etcd:

In etcd (a popular coordination service), lease acquisition uses the LeaseGrant and Put operations:

1. Grant a lease: LeaseGrant(TTL=30s) → returns lease_id
2. Put with lease: Put(key='/leader', value='node-A', lease=lease_id)
3. The Put succeeds only if no current value exists (using If conditions)
4. The key exists as long as the lease is valid
5. When lease expires, key is automatically deleted

The atomicity of Put with conditions ensures only one node can acquire leadership at a time. The automatic key deletion on lease expiry ensures leadership becomes available when the leader fails to renew.

Once a node acquires leadership, it must continuously renew its lease to maintain leadership. Renewal frequency and failure handling are crucial for system reliability.

Renewal timing:

The leader must renew before the lease expires, accounting for:

• Network latency to coordination service
• Coordination service processing time
• Clock uncertainty
• Buffer for retry attempts

Rule of third: A common heuristic is to renew at 1/3 of the lease duration:

• Lease duration: 30 seconds
• Renewal attempt at: 10 seconds
• Time for retries: 20 seconds (multiple attempts possible)
• Guard period: 5 seconds (stop acting as leader before expiry)

This gives ample time for transient failures while maintaining safety.

Renewal protocol:

while (isLeader) {
    sleep(lease_duration / 3)
    
    for attempt in 1..max_retries {
        result = renewLease()
        if (result == SUCCESS) {
            break  // renewal successful
        }
        sleep(retry_delay)  // backoff before retry
    }
    
    if (all retries failed) {
        // Cannot renew - stop being leader
        stepDown()
        return
    }
}

Network partitions are the nemesis of distributed leader election. Lease-based election provides an elegant solution that neither Bully nor Ring can match: automatic leadership expiration through time.

Partition scenario:

Consider a cluster with leader A, followers B and C, and a coordination service (CS):

Before partition:

A (leader) ← →  CS  ← → B, C (followers)

During partition:

A (leader) |  CS ← → B, C (followers)
           ↑
    Network partition

A is isolated from the coordination service and other nodes.

Lease-based resolution:

1. T=0: Partition occurs. A has lease valid until T=30.
2. T=10: A attempts renewal. Cannot reach CS. Starts retrying.
3. T=25: A has exhausted retries. Enters guard period. Stops acting as leader.
4. T=30: A's lease expires at CS. (A is already not acting as leader)
5. T=31: B or C acquires new lease. Becomes leader.
6. T+later: Partition heals. A discovers it's no longer leader. Becomes follower.

Key insight: A stopped acting as leader before a new leader was elected. There was never a moment with two active leaders.

Even with leases, a subtle safety gap exists: a leader that experiences a long process pause (GC, swap, etc.) might resume and continue acting as leader after a new leader has been elected. Fencing tokens close this gap by providing external validation of leadership authority.

The pause problem:

1. Leader A holds lease, valid until T=30
2. At T=5, A starts a long GC pause (or VM freeze)
3. At T=25, A's renewal would have been due, but A is paused
4. At T=30, lease expires. B acquires new lease.
5. At T=35, A's pause ends. A's in-memory state says 'I'm the leader until T=30'
6. A checks current time: T=35 > T=30, so lease expired. A should step down.

So far, so good—A correctly identifies it's no longer leader. But what if:

7. A had already prepared a write operation before the pause
8. That operation is now 'in flight' to external storage
9. The storage doesn't know the operation is from a stale leader
10. The write completes, corrupting data written by the new leader B

Fencing tokens solve this:

A fencing token is a monotonically increasing identifier associated with each lease grant:

1. A acquires lease, receives fencing token 42
2. A includes token 42 in all operations to storage
3. Storage accepts operations with token >= current max seen (42)
4. A pauses... B acquires lease, receives fencing token 43
5. B includes token 43 in operations. Storage accepts (43 > 42)
6. Storage updates max seen to 43
7. A resumes, sends paused operation with token 42
8. Storage rejects: 42 < 43 (stale token)

The storage system acts as a fence, blocking operations from stale leaders.

Implementing lease-based leader election correctly requires attention to numerous practical details. Let's examine the key considerations that separate robust implementations from fragile ones.