Quorum Leases

Introduction

In distributed systems built on consensus protocols like Paxos or Raft, every read operation typically requires contacting a majority of replicas.
This guarantees linearizability but comes at a significant cost: read latency is bounded by the slowest node in the quorum, and read throughput is limited by the aggregate capacity of the consensus group.
For read-heavy workloads, this is a steep price to pay when the underlying data changes infrequently.

A quorum lease is a mechanism that allows a designated replica to serve reads locally, without contacting a quorum, for a bounded period of time.
Unlike traditional leader leases (which grant read authority to a single leader), quorum leases distribute this authority across multiple replicas simultaneously, enabling read parallelism while preserving strong consistency guarantees.
The technique was formalized by Moraru, Andersen, and Kaminsky in their 2014 SoCC paper and applies broadly to any replicated state machine built on Paxos or similar consensus protocols.

Problem: Read Scalability in Consensus Systems

Consider a five-node Raft cluster.
Every linearizable read must either go through the leader (which must confirm it is still the leader by contacting a majority) or use a read-only optimization that still requires quorum confirmation.
The leader becomes a bottleneck for reads, and adding more replicas does not improve read throughput; it actually increases the cost of each operation.

Several approaches address this problem, each with tradeoffs:

1. Follower reads with stale guarantees. Followers serve reads from local state, sacrificing linearizability for throughput.
2. Leader leases. The leader obtains a time-based lease, allowing it to serve reads locally during the lease period. This helps latency but concentrates load on one node.
3. Quorum reads. Every read contacts a quorum, which is correct but expensive.
4. Quorum leases. Multiple replicas simultaneously hold leases that authorize local reads for specific data, combining correctness with read scalability.

Quorum leases occupy a unique point in this design space: they provide linearizable reads from multiple replicas without per-read quorum communication.

Mechanism

A quorum lease grants a set of replicas the right to serve reads for a particular object (or range of objects) for a bounded duration.
The core invariant is:

Any write to a leased object must be acknowledged by all lease holders before it commits.

This invariant ensures that no lease holder can serve a stale read.
If a lease holder is unreachable, the write blocks until either the lease holder responds or its lease expires.

Lease Scope

Quorum leases are typically scoped to specific objects, key ranges, or partitions rather than the entire state.
This scoping is important because the cost of a lease is paid on writes: every write to a leased key must contact all lease holders.
Fine-grained scoping limits this write amplification to the data that actually benefits from local reads.

Lease Duration and Clock Skew

Leases are time-bounded.
A lease with duration T grants the holder the right to serve local reads for T seconds from the grant time.
Because clocks across replicas are not perfectly synchronized, the holder treats its lease as valid for only T - ε, where ε is a bound on the maximum expected clock drift between any two replicas.
This guard interval ensures that the holder stops serving local reads before any other node considers the lease expired, preventing a scenario where the holder believes its lease is still active after the system has moved on.

Lease Holders vs. Quorum Members

Not every replica needs to hold a lease.
The set of lease holders is a subset of the replicas set.
The optimal set depends on workload: replicas that receive heavy read traffic benefit most from holding a lease.
Replicas that are far from clients or unreliable are poor candidates, since their unavailability would block writes to leased data.

Walkthrough

The following walkthrough describes the lifecycle of a quorum lease in a Paxos-based replicated state machine with five replicas (R1 through R5).

Step 1: Lease Grant

A client (or the system itself) requests a quorum lease for key range [K1, K50] on replicas R1, R2, and R3.

LEASE_REQUEST:
  scope: [K1, K50]
  holders: {R1, R2, R3}
  duration: 10 seconds

1. Leader proposes LEASE_GRANT through consensus log.
2. LEASE_GRANT is committed once a write quorum (majority) accepts.
3. R1, R2, R3 record lease start time using local clocks.
4. Lease is active: R1, R2, R3 may serve local reads for [K1, K50].

Step 2: Serving Local Reads

When R2 receives a read request for key K17:

function handle_read(key):
    if holds_valid_lease(key):   // includes clock check with skew margin
        return local_state[key]  // No quorum contact needed
    else:
        return forward_to_leader(key)  // Fall back to quorum read

R2 checks that its lease is still valid (accounting for clock skew) and returns the local value.
No network round trips are required.

Step 3: Writing to Leased Data

A client submits a write to key K30, which falls within the leased range.

function handle_write(key, value):
    if key is covered by active lease:
        // Must notify ALL lease holders, not just a quorum
        ack_set = send_invalidate_or_update(key, value, lease_holders)
        if ack_set == lease_holders:
            commit(key, value)
        else:
            wait until missing holders respond OR their leases expire
            commit(key, value)
    else:
        // Normal quorum write
        propose_via_consensus(key, value)

The critical detail: the write cannot commit until every lease holder has acknowledged it; this is stricter than the normal quorum requirement.
If R3 is temporarily unreachable, the write to K30 blocks until either R3 responds or R3's lease expires (at most 10 seconds in this example).

Step 4: Lease Renewal

Before the lease expires, the system can renew it through the consensus log:

LEASE_RENEW:
  scope: [K1, K50]
  holders: {R1, R2, R3}
  new_duration: 10 seconds

1. Renewal is proposed and committed via consensus.
2. Lease holders update their local expiry times.
3. If renewal fails (e.g., leader changes), lease expires naturally.

Step 5: Lease Expiration

If the lease is not renewed, it expires silently.
After expiration, R1, R2, and R3 stop serving local reads and fall back to quorum reads.
Writes to [K1, K50] no longer need to contact the former lease holders.

Correctness Argument

The linearizability argument for quorum leases relies on two properties:

Property 1: Write visibility. Every write to a leased key must be acknowledged by all current lease holders before it commits.
Therefore, at the moment a write commits, every lease holder has applied it to local state.
Any subsequent read from any lease holder will reflect that write.

Property 2: Lease expiry as a safety boundary. A write to a leased key can only commit after all lease holders acknowledge it, or after waiting for non-responsive holders' leases to expire.
In the latter case, the write does not commit until the lagging holder's lease has definitively ended.
Once that holder's lease expires, it stops serving local reads and reverts to quorum reads — at which point it cannot return a value without consulting a quorum that will include the committed write.
There is therefore no window in which a stale local read can occur.

The combination ensures linearizability: every read returns a value consistent with the total order of committed writes.

The primary vulnerability is clock skew.
If a lease holder's clock runs fast, it may believe its lease is still valid after the rest of the system considers it expired.
The standard mitigation, described in the Lease Duration section above, is to shorten the effective lease duration on the holder's side by a margin ε that exceeds the maximum expected clock drift.

Operational Considerations

Log compaction and snapshots. When a replica applies a snapshot during log compaction or catches up after a partition, it must also restore the current lease state.
Because leases are recorded in the consensus log, they are included in snapshots.
However, implementors must ensure that a replica resuming from a snapshot does not serve local reads for a lease that has since been revoked or transferred.

Interaction with leader failover. When a leader fails, the new leader must be aware of outstanding leases.
Leases are recorded in the consensus log, so a new leader can reconstruct the lease state.
In-flight writes that were waiting for lease holder acknowledgments may need to be retried by clients.

Tradeoffs and Design Considerations

Write latency vs. read latency. Quorum leases shift cost from reads to writes.
Local reads become fast (single-node latency), but writes to leased data become slower (must contact all lease holders instead of just a quorum).
This tradeoff is favorable when the read-to-write ratio is high.

Availability impact. A single unavailable lease holder can block writes for up to the lease duration.
Shorter leases reduce the worst-case write stall but increase renewal overhead.
The system must choose lease durations that balance write availability against renewal cost.

Lease granularity. Coarse-grained leases (e.g., entire tables) simplify management but amplify write costs.
Fine-grained leases (e.g., per-key) reduce write overhead but increase metadata and renewal traffic.
In practice, range-based leases offer a reasonable middle ground.

Number of lease holders. More lease holders increase read throughput but increase write latency and reduce write availability.
The optimal number depends on the workload's read/write ratio and the reliability of individual replicas.

Comparison with Leader Leases

Leader leases grant a single node the right to serve local reads.
They are simpler to implement but create a read bottleneck at the leader.
Quorum leases generalize leader leases by distributing read authority.
The cost is increased write complexity and the requirement that writes contact all lease holders.

Systems such as Spanner use time-based leader leases for linearizable local reads at the leader replica.
CockroachDB has explored both leader leases and follower read mechanisms; specific implementations vary across versions.
Quorum leases offer an alternative when read traffic is too high for a single leader to handle, or when geographic distribution makes it desirable to serve reads from replicas closer to clients.

Key Points

• Quorum leases allow multiple replicas to serve linearizable reads locally without per-read quorum communication.
• The core invariant requires every write to a leased key to be acknowledged by all lease holders before committing.
• Write latency and availability degrade for leased data, making quorum leases most effective for read-heavy, write-light workloads.
• Clock skew is handled by reducing the effective lease duration on the holder's side by a margin exceeding the maximum expected drift.
• Lease granularity (per-key, per-range, and per-table) controls the tradeoff between metadata overhead and write amplification.
• Quorum leases generalize leader leases by distributing read authority across multiple replicas.
• Lease expiration provides a natural recovery mechanism: if a lease holder becomes unreachable, writes block for at most the remaining lease duration.
• Log compaction and snapshot transfers must preserve lease state to avoid serving stale reads after recovery.

References

Moraru, I., Andersen, D. G., and Kaminsky, M. "Paxos Quorum Leases: Fast Reads Without Sacrificing Writes." Proceedings of the ACM Symposium on Cloud Computing (SoCC), 2014. (Primary source for quorum leases.)

Moraru, I., Andersen, D. G., and Kaminsky, M. "There Is More Consensus in Egalitarian Parliaments." Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP), 2013. (EPaxos; background on leaderless Paxos variants.)

Lamport, L. "The Part-Time Parliament." ACM Transactions on Computer Systems, 16(2), 1998.

Ongaro, D. and Ousterhout, J. "In Search of an Understandable Consensus Algorithm." Proceedings of the 2014 USENIX Annual Technical Conference (ATC), 2014.

Corbett, J. C., Dean, J., Epstein, M., et al. "Spanner: Google's Globally-Distributed Database." Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2012.