Quorums, consensus, leases, and fencing

01What are quorum, consensus, lease, and fencing?

A service that replaces failed workers has two problems: agree which worker is now authorized, and prevent a previous worker from publishing afterward. The following mechanisms handle different parts of that handover.

Keep four definitions separate:

1. Quorum: a protocol-defined set of participants whose votes or replies are sufficient for an operation to proceed, often a majority.
2. Consensus: agreement on a decision or ordered history despite failures within the protocol’s model.
3. Lease: permission that expires after a defined time.
4. Fencing token: a monotonically increasing ownership number checked by the protected resource to reject outdated writers.

These are not four names for a distributed lock. Quorum rules can require read and write groups to share a replica. Consensus makes the controllers agree on the sequence of ownership changes. A lease limits permission in time. Fencing lets the output store reject a write carrying an older ownership number. Start by keeping those responsibilities separate.

Publishing the result of a job shows why agreeing on its owner and protecting its output are separate tasks. Export E9 reads records, writes an output file, and publishes its location in a manifest. One worker can own the job initially, but recoverable execution needs a replacement owner after failure. The replacement decision and rejection of stale publication are separate requirements.

We introduce an ownership record: E9 → worker W1, epoch 7. An epoch is a number that increases whenever the job is assigned a new owner. W1 may work while its time-limited permission, called a lease, remains valid. Three controller replicas store this permission so losing one controller need not lose the job’s ownership history.

At 12:00:02 W1 pauses for twelve seconds. The controllers later expire its permission and assign W2. A paused process is not dead: W1 can resume with its old instructions. Our design must answer two different questions: how do controllers agree on the new owner, and how does the output store stop the old owner? All times and numbers in this lesson are hypothetical.

02Quorum arithmetic: N, R, W, and overlapping sets

For N = 3, W = 2, and R = 2:

Every read has a chance to encounter the acknowledged version. If W is also greater than N/2, any two write groups overlap. One unavailable controller still leaves two participants, but two unavailable controllers leave too few for these operations. These counts describe the chosen fixed membership and response requirements.

There are two counts to keep separate. For simple majority consensus, N = 2f + 1 participants can continue with f unavailable when the remaining majority communicates and the protocol's timing assumptions eventually hold. Four voters still need three votes and tolerate only one unavailable voter; five need three and tolerate two. Membership changes must themselves follow the protocol: changing N independently on different clients invalidates the fixed-set intersection argument.

03Why quorum overlap alone is not a consistency protocol

Suppose a failed update proposing owner version 9 reaches only R1. One read consults R1 and R2 and completes with 9. Only after that response, another read starts, consults R2 and R3, and returns 8; no new ownership update occurred between these reads. Both read groups have size two, yet clients have observed a reversal unless the protocol handles that incomplete write correctly.

We need rules for valid versions, concurrent updates, failed attempts, and read completion. “Take the largest timestamp” is not automatically correct: clocks can disagree and an incomplete proposal may not be committed. Using substitute nodes during a failure also changes the overlap assumptions. This is one reason Dynamo’s quorum-style techniques must be understood with their surrounding protocol.

For E9’s ownership, we want one agreed committed history. We therefore choose an established consensus protocol rather than invent a lock service from the arithmetic alone. A quorum contributes to the proof; it is not the whole proof. The extra discipline costs coordination and can stop progress without enough connected participants.

A pending write is allowed to take effect even if its caller never receives success. The error in the trace is returning 9 and then reverting to 8 with no intervening write. Some atomic read/write-register protocols address this by making a reader propagate the selected version to a quorum before returning. The Attiya–Bar-Noy–Dolev register is a classic example. That is a different protocol from a one-round 'read two and return the maximum' rule, and from consensus on arbitrary ownership commands.

A sloppy quorum may acknowledge on substitute nodes outside a key’s normal replica set when home replicas are unavailable. For home replicas A/B/C, two substitutes D/E can accept a write while a read of A/B sees the old value. Counting W=2 and R=2 against N=3 does not prove overlap because those responses came from different sets. Hinted handoff can later deliver the missed data to home replicas. This improves write availability under the chosen contract, but adds repair work and does not supply an immediate latest-value read guarantee.

04Consensus with Raft: leaders, terms, and committed logs

Consensus lets a group agree on state transitions under a defined failure model. In a replicated-log approach, replicas apply the same committed commands in the same order. For E9, that sequence includes assigning W1, expiring its ownership according to the lease policy, and granting W2 epoch 8.

Raft organizes this around a leader, followers, and election terms. A term is a generation of controller leadership, distinct from E9’s job-ownership epoch. The leader replicates log entries; election and commit rules preserve committed history across leader changes. A majority of three is two; a majority of five is three. These are crash-fault protocols, not a claim that any malicious participant can be tolerated. Raft paper.

At 12:00:11, the controllers agree that W2 owns the job under epoch 8. A controller with old data must not grant the job again. Before reporting the current owner, it must also perform the protocol’s check that its answer is current. A recent timestamp alone cannot prove that.

Raft: election, replication, commitment, application

1. Elect. A candidate gains a majority with the required log-freshness check.
2. Replicate. The elected leader replicates an entry from its current term.
3. Commit. That entry is committed after the specified majority accepts it.
4. Apply. Replicas apply committed entries in order.

A majority containing an old-term entry alone is not enough to infer that entry is committed. For a linearizable read without appending each read, the leader must establish current authority, know the committed position, and apply through it before answering. These rules explain why the label “leader” is insufficient.

Basic Paxos: prepare, select, accept

Paxos is another consensus protocol. Basic Paxos chooses one value using proposers and acceptors:

A proposer asks the group to choose a value. Acceptors retain promises and accepted proposals so later attempts can discover earlier decisions. A ballot is a uniquely ordered proposal-attempt identifier; a higher ballot gives an attempt priority, not permission to replace an already chosen value.

1. Prepare. A proposer with a unique higher ballot asks a majority to promise not to accept lower ballots. Replies report previously accepted values.
2. Select the safe value. Carry forward the value from the highest accepted ballot learned, if any; otherwise propose a new value.
3. Accept. A majority accepting that ballot/value makes the value chosen. Durable promises and accepted state protect recovery.

The rule for carrying an earlier value forward, together with intersecting majorities, prevents two different chosen values. Repeated competing proposals can prevent progress; practical systems use leadership and sufficient communication stability. Multi-Paxos builds an ordered log from repeated decisions, often amortizing preparation under stable leadership. Like Raft, it is more than majority arithmetic and is distinct from two-phase commit across independent databases.

Interview check: Can a new proposer ignore a previously accepted value because it has a larger ballot? No; the prepare replies constrain the value it may safely propose.

05Fencing tokens: reject stale writers at the resource

The controllers agree that W2 owns E9, but the output store still receives worker requests independently. Each publication therefore includes the agreed ownership version (epoch) as a fencing token. When updating the manifest, the store checks that version atomically. Otherwise, a paused old worker could resume and overwrite W2’s result despite the controllers’ agreement.

W2 finishes quickly. At 12:00:12 it asks the output store to publish file E9-v8 with fence 8. The store atomically compares the fence with its latest accepted ownership generation and records the new manifest. At 12:00:14, W1 resumes and submits E9-v7 with fence 7. The store rejects it because 7 is older than the accepted 8.

Persist the highest accepted fence with the manifest so a resource restart cannot forget token 8. Scope that number to the protected job/resource, and accept only tokens issued through an authenticated ownership path; an arbitrary client-supplied large integer is not authority. A repeated token 8 may be valid, so deduplicate its operation separately. This design prevents a lower-generation write after the store has accepted the higher generation; it does not promise that only one worker ever computed an output.

06Leases, fencing, and idempotency solve different failures

An idempotency key solves a different problem: repeating the same valid publication attempt. Fence 8 can be valid for several W2 requests; it does not identify which repeated request is the same operation. Use a stable publication identifier and a conditional manifest change when duplicate effects matter.

Some stores support checking an ownership key in the same transaction as the data update. etcd’s concurrency API exposes ownership keys for that pattern. An unrelated external service is not automatically inside that transaction. Keep consensus on small critical ownership metadata where useful; copying the export’s large file bytes need not pass through the controller log.

For time-based permission, state which service evaluates expiry and which clock assumptions the implementation uses. A worker's cached wall-clock check is not a resource-side authorization check. Clock jumps and long pauses are reasons to use a proven lease implementation and have the output store check permission as part of the publication itself.

07Interview answer: a paused worker returns after takeover

Interviewer: “The lease expired, so why can’t W2 just continue?”

Candidate: “The controllers can agree that W2 owns the job while W1 is only paused. When W1 resumes, it may still try to publish its old result. I attach epoch 8 to W2’s request and make the output store check it atomically when saving. The store rejects older epochs. The controllers choose the owner; fencing makes the store enforce that choice.

“If the controllers lose their majority, I would stop granting new ownership under this protocol rather than invent two histories. Existing work must obey its remaining permission and publication rules. After recovery, I would reconcile the committed ownership record, the latest published manifest, and any abandoned files.”

This answer names what the quorum, consensus log, lease, fence, and idempotency key each contribute. None is a general replacement for the others. The failure drill includes controller loss, an isolated controller, a paused worker, and a publication whose response is lost.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.