269: Consensus, Leader Election, Distributed Locks, and Coordination

Learning outcomes

By the end of this lesson, you should be able to:

explain the consensus problem and apply it to a realistic implementation;
explain leader election and apply it to a realistic implementation;
explain fencing tokens and apply them to a realistic implementation;
explain distributed locks and apply them to a realistic implementation;
explain quorum availability and apply it to a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before you read, retrieve one concrete example from a previous project where one of these concerns appeared. Perhaps two workers could process the same job, two requests could update the same record, or a service had to decide whether it was still allowed to act. The point is not to memorize terminology. It is to practice making a defensible decision inside a large-scale distributed service, where requirements, traffic, failure modes, cost, and operational constraints all need to be explicit.

Terminology

Consensus problem: A group of nodes needs to agree on values or an order of values despite failures.
Leader election: Elect one active coordinator for a shard or job when duplicate leaders would violate correctness.
Fencing tokens: A monotonically increasing token attached to a lock or lease holder lets the protected resource reject stale holders. This addresses pauses and network partitions in which a client incorrectly believes its lock is still valid.
Distributed locks: Use a proven coordination system and define lease expiration, renewal, ownership, and fencing rather than treating a lock as a complete correctness mechanism.
Quorum availability: A consensus group typically needs a quorum to make progress. Losing too many members sacrifices availability in order to preserve one authoritative history.
Avoiding coordination: Partition work by key, use idempotency, use commutative operations, or use single-owner queues when possible.

These terms are related, but they are not interchangeable. Consensus is about agreement on shared state or ordering. Leader election uses an agreement mechanism to assign authority. A distributed lock usually grants temporary ownership, and fencing makes that ownership safe against a delayed or partitioned client. Quorum is the availability rule that determines whether the group can safely make progress. In many designs, the best coordination mechanism is to arrange the work so that global coordination is unnecessary.

Mental model

Treat Consensus, Leader Election, Distributed Locks, and Coordination as a design problem with observable inputs, outputs, invariants, and failure modes. Coordination primitives exist to agree on small pieces of critical distributed state. They are not free: they add latency, operational dependencies, and more failure cases. If partitioned ownership can avoid global agreement, it is usually the simpler design.

A strong implementation makes its assumptions visible, narrows uncertainty at system boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe. Start with the property that must remain true, not with the API offered by a coordination library.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

For example, “only one worker may publish the result” is a requirement. The constraints might include worker pauses, retries, a partitioned network, and a non-transactional downstream API. The model then has to say what ownership means, how it expires, and how the downstream resource rejects stale work.

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it. This distinction matters because a lock can prevent two healthy clients from entering a critical section while still failing to stop an old client that wakes up after its lease has expired.

Deep dive

1. Consensus problem

The practical problem appears when several nodes must make one authoritative decision while some nodes may crash, pause, or become unreachable. A group of nodes needs to agree on values or an order despite those failures. Practical consensus protocols such as the Raft and Paxos families rely on quorum and leadership assumptions; they are more than a simple “majority vote.”

The agreed result normally needs a durable ordering or history so that nodes that rejoin can converge on the same state. A quorum helps prevent two incompatible histories from both being treated as authoritative. That safety comes with a cost: if the group cannot contact enough members, it may be unable to accept new decisions even though some individual nodes are still running.

Decision rule: Use consensus deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Ask what shared decision actually requires agreement, how a node learns that a decision is committed, and what the system does when quorum is unavailable.

2. Leader election

Leader election is useful when one active coordinator must own a shard or scheduled job. The goal is not merely to assign a label called “leader”; it is to ensure that duplicate leaders cannot perform work that would violate correctness. The election mechanism needs leases, terms, or epochs so that an old leader cannot continue acting after losing authority.

This is where people usually get confused: a process can be alive and still no longer be the leader. A network partition may prevent it from learning that another node has been elected, and a stop-the-world pause may keep it from renewing its lease on time. Every operation performed under leadership therefore needs a way to establish that the authority is current.

Decision rule: Use leader election deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State what the leader owns, how a term changes, how followers reject stale terms, and whether a lease failure pauses work or causes it to be retried.

3. Fencing tokens

Suppose worker A acquires a lease and then pauses. Its lease expires, so worker B acquires a newer lease and begins processing. If A resumes, it may still believe that its lease is valid and send a write to the protected resource. A lock service alone cannot necessarily prevent that write.

A fencing token addresses this case. The coordination service gives each lock or lease holder a monotonically increasing token. The protected resource stores or compares the highest token it has accepted and rejects an operation carrying an older token. The token turns “I currently believe I own the lock” into an assertion the resource can verify.

The resource must actually enforce the token. Passing a token around in application memory without checking it at the database, storage service, or other protected boundary does not provide fencing. The token also does not make an unrelated non-transactional side effect atomic; it only lets the resource reject stale ownership claims when that resource supports the check.

Decision rule: Use fencing tokens deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Confirm where the token is generated, where it is persisted or compared, and what an older token receives as its failure response.

4. Distributed locks

A distributed lock coordinates clients that may run on different machines. Use a proven coordination system and define lease expiration, renewal, ownership, and fencing. A lock service does not make non-transactional external work magically safe. For instance, acquiring a lock and then calling a payment provider are not one atomic operation merely because the call happened inside a locked code block.

You need a clear answer for each lifecycle event: what happens when the holder crashes, when renewal is delayed, when the client loses connectivity, and when the client receives a timeout without knowing whether the lock operation succeeded. Release must also identify the owner so one client cannot accidentally release another client's lock after a retry or delayed response.

Decision rule: Use distributed locks deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. Consider idempotency, transactions, a single-owner queue, or partitioning before introducing a lock, and add fencing when a stale holder could still reach the protected resource.

5. Quorum availability

A consensus group typically needs a quorum to make progress. In a group of N members, the exact quorum rule belongs to the protocol, but the general trade-off is consistent: the group may reject new decisions when too many members are unavailable so it can preserve one authoritative history. A running minority is not automatically safe to write.

This creates a deliberate availability trade-off. During a failure, a system that keeps accepting conflicting writes could appear available while making recovery and reconciliation unsafe. A system that stops writes without quorum is less available, but it protects consistency. Operational planning therefore includes member placement, failure domains, recovery time, and the capacity needed to tolerate the expected loss of members.

Decision rule: Use quorum availability deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Document how many failures the group tolerates, which operations require quorum, and what callers observe when the group cannot make progress.

6. Avoiding coordination

Many coordination problems disappear when work is partitioned by key. A single owner can process each account, order, or inventory item, while retries are made idempotent and independent operations are designed to commute. A single-owner queue can also serialize the small part of the workload that truly needs ordering without forcing every worker to agree globally.

The fastest consensus is often not needing consensus for that operation. This does not mean avoiding coordination at any cost. If two writers can affect the same invariant and neither can safely determine ownership, removing the coordination mechanism may simply hide a race. The design still needs an explicit explanation of why partitioning, idempotency, or commutativity is sufficient.

Decision rule: Use avoiding coordination deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Identify the partition key, its hot spots, the behavior for missing keys, and the recovery path when an owner fails.

Worked example

Consider a large-scale distributed service whose requirements, traffic, failure modes, cost, and operational constraints must be made explicit. Start by writing the requirement in one sentence. Then list the input and output contracts and identify which concept owns each failure mode. For example, a scheduled singleton job may require one active worker per shard, while inventory batch processing may require a lease, renewal, fencing token, and an idempotent batch result.

The important move is separation. Parsing and validation belong at the boundary. Domain rules belong in the domain or service layer. Persistence rules belong in the database or repository. Presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes concurrency and edge cases much harder to reason about.

Client
  |
DNS -> CDN / Edge
  |
Load Balancer -> API instances -> Cache
                          |          |
                          +------> Primary datastore
                          |
                          +------> Queue / Stream -> Workers

Read the diagram as a set of boundaries, not as proof that every request must visit every component. DNS and the edge route the client; the load balancer distributes requests; API instances apply service rules; the cache and primary datastore hold state; the queue or stream transfers asynchronous work to workers. Coordination may be needed among workers, but it is not a substitute for validation, persistence constraints, or authorization.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate, retry, or concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. In the concurrent path, also state whether the operation is rejected, serialized, made idempotent, or protected by a current fencing token. In a dependency failure, distinguish a timeout from a confirmed rejection: a timeout may leave the outcome unknown and require a safe retry strategy.

This is the level of explanation expected in a senior code review or technical interview. The design is not complete until it explains both the successful operation and the behavior of a delayed, duplicated, or partially disconnected participant.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality workloads. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. A timeout bounds how long a caller waits, but it does not necessarily prove that the remote operation did not happen. When the topic involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and all network input is untrusted.

For coordination specifically, monitor lease acquisition latency, renewal failures, leadership changes, quorum loss, rejected stale tokens, lock contention, and work retries. These signals help distinguish an application bug from a coordination-service outage or a pause that exceeded the lease. Keep the operational response explicit: some failures should stop writes, some should retry, and some should be safely ignored as duplicate work.

Guided lab

Design leader election for a scheduled singleton job and a lock for inventory batch processing. Add fencing tokens, and describe what happens when the holder pauses beyond its lease and then resumes. Your design should state what the job is allowed to do under a term, how the next holder receives a larger token, and how the inventory resource rejects the resumed holder's stale token.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the pause scenario, do not stop at “the lock expires.” Follow the message path. The old holder may resume, make a request, and receive a rejection from the protected resource because its fencing token is lower than the current token. That rejection is the expected safety behavior, not necessarily an infrastructure defect. Also record whether the unfinished batch is retried and whether the result is idempotent.

Edge cases and failure modes

Consensus problem: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test member loss, a lack of quorum, a delayed response, and a node rejoining with stale state.
Leader election: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Test lease expiry, a renewal failure, simultaneous election attempts, and an old leader acting after a newer term has been issued.
Fencing tokens: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Test monotonic token assignment, a stale token at the resource boundary, repeated requests, and a holder that resumes after a long pause.
Distributed locks: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Test crash recovery, renewal delay, release by the wrong owner, lock-operation timeouts with unknown outcomes, and contention.
Quorum availability: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Test each credible member-loss scenario, the transition into and out of quorum loss, and the caller-visible behavior while progress is intentionally refused.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Treating a lease as permanent ownership, or assuming that a lock service can cancel work already sent to an external system.
Generating fencing tokens without enforcing them at the resource that must reject stale work.
Treating a timeout as proof that a distributed operation failed when the remote side may have committed it.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, and trace the boundary where the invariant first becomes false. For coordination, inspect the holder identity, lease or term, token, renewal timestamps, quorum state, and the resource's accepted token. Compare those facts with the logs from the coordinator and the protected resource rather than trusting the client's local belief.

Then fix the owning layer instead of adding a downstream patch. A malformed request belongs at the boundary, an invalid state transition belongs in the domain or persistence layer, and a stale holder must be rejected where the protected state is written. Check whether the abnormal result is a safety failure, an intentional availability refusal, an ambiguous timeout, or merely a retry that was not made idempotent.

Interview questions

What problem does the consensus problem solve, and what trade-off or failure mode would make you choose a different approach?
What problem does leader election solve, and what trade-off or failure mode would make you choose a different approach?
What problem do fencing tokens solve, and what trade-off or failure mode would make you choose a different approach?
What problem do distributed locks solve, and what trade-off or failure mode would make you choose a different approach?
What problem does quorum availability solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Consensus, Leader Election, Distributed Locks, and Coordination to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. As a final check, explain where a stale leader is rejected and what the caller sees when quorum is unavailable.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.