Lesson browser Distributed consensus, replication, and fault tolerance lessons Previous: Paxos and preserving an earlier decision Next: Retries and the boundary of exactly once

Distributed systems · Lesson 11

Safe reads, leases, and fencing

Understand stale leaders, read barriers, and protection against delayed owners.

By the end: Identify the evidence a server needs before a read or an external write is safe.

A leader can be alive and obsolete

A is isolated from B and C but still reachable by some clients. B and C elect B and commit a write. A’s old local state is now stale even though its process is healthy. Answering a read solely because A’s local role says leader can violate linearizability. A successful earlier election does not prove current authority forever.

One safe Raft strategy is to put a read-related barrier through the replicated log and wait until the required prefix is applied. An optimized read-index style path avoids logging every read but still needs proof of current authority and a safe committed boundary. At the start of a term, committing a current-term entry establishes needed commit knowledge. For the read, quorum contact in the appropriate term confirms authority, and the serving state machine must have applied through the safe read index before returning data.

A read needs authority and sufficiently applied state

Begin with a separate three-server case. A led an earlier term and applied through index 40. A network partition now separates A from B and C. B wins a later election with C and commits index 41, which changes a price from 8 to 9. A client receives success for that change, then asks A for the current price. Returning 8 would violate real-time precedence for the register-like price operation. A has an internally consistent state through index 40. Its problem is that this state no longer supports the current-read promise.

A second case isolates another failure. B is unquestionably the current leader and knows index 41 is committed, but its application worker has only applied through 40. The durable log contains the new price while the state machine still contains 8. Returning the application value immediately would again be stale. Quorum contact cannot substitute for executing the committed prefix. Conversely, applying every entry a server knows cannot establish that the server knows all required entries. Current authority and sufficient application progress are independent requirements. A linearizable read path must establish both.

A read-index style procedure records a safe committed boundary for the read and uses suitable same-term quorum communication to establish leadership authority. The messages must belong to this read procedure, or a correctly justified shared batch of reads. Yesterday's heartbeat replies do not establish authority for today's newly arriving request. The serving state machine waits until its applied index reaches the safe boundary. If application is behind by three entries, that wait is for actual execution of those entries, not merely for their presence in storage.

At the beginning of a new Raft term, commit knowledge needs special care. A leader can inherit committed entries without yet knowing which inherited entries were committed. Committing an entry from its own current term establishes a safe prefix using Raft's commitment rules. That entry can be a no-op, meaning a command that changes no application data. It still occupies a log position and requires the normal durable majority. Counting inherited older-term copies alone is not the substitute. Election term describes this leadership attempt; an inherited entry retains the term in which it was created.

A follower can sometimes serve the data for a read if a correct protocol gives it a safe boundary and it waits to apply through that boundary. This does not mean an arbitrary follower may use its local commit index indefinitely. The authority evidence must cover the read, and the returned data must correspond to an allowed point in the read's invocation-to-response interval. An explicitly stale read has a different contract and may avoid this coordination. Giving both APIs the same name without stating their guarantees makes client reasoning unreliable.

A lease is a timing-dependent permission

A lease grants authority for a bounded interval according to specified clock and delay assumptions. It can reduce coordination during reads, but safety now depends on how the holder and grantor interpret expiration. Clock drift, pauses, and message delays matter. A process paused while its lease expires cannot simply resume and assume that a remembered permission still holds.

Distinguish a monotonic elapsed-time clock from a wall clock that may jump after synchronization. Even a monotonic clock does not by itself settle behavior across process suspension or all hardware conditions. A correct lease algorithm states its clock bounds, grant rules, and safety margin. Reading a timestamp and subtracting it from local now is not a complete lease proof. Systems with bounded clock uncertainty may delay responses until an ordering claim is safe; the waiting is part of the guarantee.

Read barriers do not freeze the cluster

Linearizability permits a read to overlap a write without observing that write. Suppose a read begins, establishes a safe boundary at index 52, and waits while index 52 is applied. A concurrent writer then commits index 53 before the read response reaches the client. Returning the state at 52 can be legal because the read can take effect before the overlapping write. The read does not have to chase the newest index forever. It needs a legal position within its own interval and must include all writes that completed before it began.

Compare that case with a write at 53 that completed before the read's invocation. A boundary selected for the read must not omit that completed write. This is why a cache of an old read index is not a timeless certificate. A correct read protocol connects the request's timing to authority and commitment evidence. In a paper history, draw invocation and response intervals first, then ask which write completions constrain the read. Do not decide legality by looking only at the numeric distance between its returned version and the last version visible afterward.

A log-based barrier offers a more explicit route. Submit an operation through the authoritative log and wait until the required committed prefix has been applied before taking the associated read. Its position gives an ordering point. This consumes replication work even if it changes no application field. A read-index optimization avoids appending one entry for every read, but removes no safety obligation. Its benefit is avoiding some log work, not permission to skip authority checks. Neither route follows automatically from the fixed-leader replication experiment earlier in the course.

Now consider a lease without assuming a particular product's algorithm. If grantors promise not to authorize a competitor during a real interval, a holder needs a conservative local interval contained within that promise. Message delays can make a grant arrive after much of its useful interval has elapsed. Clock rates can differ, so equal durations measured independently need not cover equal real intervals. Starting the holder's timer only when a delayed reply arrives can extend its apparent permission past the grantor's promise. A valid design must rule out that overlap.

Pauses add another case. A worker checks that a lease is valid, stops running for a while, and then resumes at the next instruction. The previous check does not authorize an action at the later instant. A monotonic clock avoids backward wall-clock adjustments, but its behavior during suspension and its rate bounds still belong in the model. Without specified grant rules and clock assumptions, no safe duration can be derived from a timestamp alone. The table that follows concerns resource-enforced tokens instead. It does not simulate clock drift or validate a lease algorithm.

Work through the model

Time order	Coordinator or resource	Old worker
1	Grant token 41	Starts work, then pauses
2	Grant 42; resource accepts 42	Still paused
3	Resource rejects 41 < 42	Resumes with obsolete authority

The enforcement point is the resource, not the paused worker’s memory of being leader.

A token orders resource actions rather than worker beliefs

Read the displayed token sequence as a statement about the protected resource. The old worker remembers 41 while paused. The new worker obtains 42 and the resource accepts an action carrying 42. Only then does the shown rejection of 41 follow from the resource's stored maximum. Issuing 42 at the coordinator does not itself inform an unrelated file server. If 41 reaches that server before any higher token, a simple highest-seen check may still accept it. Fencing provides an order at the enforcement point, not instantaneous revocation everywhere.

In a separate paper case, give a resource a stored maximum of 60. Request X carries token 61 and a replacement file. Request Y carries token 60 and an older replacement. If X commits first, the resource stores 61 and the new file atomically, so Y must fail. If Y commits first, X may subsequently replace it under the higher authority. There is no accepted lower-token action after the higher-token action. That is the specific protection. It does not imply that the old worker performed no computations or that every prior effect can be reversed.

Atomicity here means no other action can enter between the token decision and its protected mutation. Suppose a resource checks 60 against maximum 60, pauses that request, then accepts 61 and updates the file. If it later resumes the earlier request and writes without rechecking, the stale overwrite succeeds despite a token check somewhere in the code. The comparison and write need one serialized state transition. The maximum must also survive the failures against which fencing is promised. Forgetting it after restart can reopen access to previously rejected authorities.

Token equality needs a separate policy. A worker may legitimately issue several actions under token 61. Rejecting every equal token would permit only one such action, while allowing equal tokens does not prevent a retry from repeating a charge. Tokens normally distinguish authority epochs rather than individual business operations. A per-operation identity and a durable deduplication rule can handle repeats within an epoch. If several updates under one token require an order, a resource may need sequence checks or another operation-ordering rule. A larger authority number alone does not order all commands from that authority.

Explore the table by writing each event beside two state columns, coordinator's latest issued token and resource's highest accepted token. Advance only the column changed by that event. During a delay those numbers can differ. This exposes the exact point where the resource can reject an obsolete action. It also shows why worker-side checks are insufficient. A paused worker cannot enforce a decision at a resource that never sees the authority evidence. This is a paper extension of the static table, not a control offered by the page.

Fence old owners at the protected resource

A fencing token is a monotonically increasing authority number issued by a trusted coordination mechanism. The actual resource remembers the highest accepted token and rejects writes with older tokens. Suppose an old worker with token 41 pauses. A new worker obtains 42 and writes. When 41 resumes, the storage service itself rejects 41 rather than trusting the worker to notice its expired lease.

Token checks must be atomic with the protected action and durable across the relevant failures. Checking once at the worker and then issuing an unfenced write leaves a race. Fencing orders accepted authorities; it does not undo a completed external action or turn a non-idempotent request into an idempotent one. The resource’s API and failure model determine whether this pattern can protect it at all.

Define which resource the authority protects

A token must have a defined scope. Suppose coordination issues increasing tokens separately for file A and file B. Token 8 for A cannot be compared meaningfully with token 12 for B unless the system explicitly defines a shared authority order. The resource should associate its remembered maximum with the same protected object or authority domain used by the coordinator. Otherwise, an unrelated operation can incorrectly fence valid work or an old operation can evade the intended comparison. Monotonicity is a property of a specified sequence, not every number in the system.

Resource enforcement also requires trustworthy issuance and request attribution. If any worker can invent token 1000000, numerical comparison alone lets it displace legitimate owners. Authentication can establish that an authorized coordinator issued a token or that a particular worker sent a request. It does not prove that an authorized worker behaves honestly. The crash-fault examples assume participants follow their protocols and do not forge authority evidence. A system facing malicious clients or workers needs access control and evidence validation in addition to an ordered counter. This lesson's token table is not a Byzantine protocol.

Protection across several resources requires separate reasoning. A worker can update one fenced file and crash before updating a second. Each file may reject stale owners correctly while the pair contains an incomplete business operation. Fencing prevents a particular class of stale-authority action. It does not provide an atomic transaction across the files. Likewise, protecting a database row does not protect an external email or payment that bypasses that row's enforcement. Locate the actual irreversible mutation before claiming that a lock, lease, or token covers it.

For a final guided case, imagine a report worker that reads a price, computes an invoice, and later submits it to storage. A linearizable read can establish a valid price observation during the read interval. It does not promise that the price stays unchanged throughout computation. A fencing token can exclude an older worker's delayed write after a newer token has been accepted. It does not establish that the invoice used the current price at submission. That business rule needs its own atomic version check or transaction at the relevant authority.

These distinctions determine the failure response. A server lacking current read authority should wait, redirect, reject, or explicitly offer a weaker read contract. A worker rejected by fencing must not retry the same obsolete action without tokens. A current worker uncertain whether its action completed needs an operation-status or retry contract, rather than a new authority number alone. The next lesson develops stable request identities and atomic durable result records. Those records solve duplicate business effects, a different problem from stale leadership and insufficiently applied state.

Exercises

A local leader read

A served a write yesterday and still calls itself leader. Today B+C elected another leader while A was partitioned. Is A’s cached leadership enough to answer a linearizable read?

Hint

Yesterday’s election says nothing about an unseen later term.

Worked answer

A knows	A does not know	Consequence
Its old election	B+C’s new term and writes	Local role can be stale

Leader belief alone is not a read barrier.

No. It needs a valid read protocol with current authority and sufficient applied state, or a correctly specified unexpired lease. Without that evidence it must not promise a current linearizable read. An explicitly stale read is a different API contract.

Where must fencing happen?

A worker checks token 7, pauses, then sends a file write after token 8 has been used. The file server never sees tokens. Is this protected?

Hint

The worker’s check and the resource modification are separated by a pause.

Worked answer

Action	Worker-only check	Resource-enforced token
Token 8 write	Accepted	Accepted; highest becomes 8
Delayed token 7 write	May overwrite	Rejected as stale

The token must travel with the action it protects.

No. The file server must receive and enforce the token, or an equivalent atomic authorization mechanism must protect the modification. A precheck outside that resource cannot reject the stale delayed write.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Ongaro and Ousterhout: In Search of an Understandable Consensus Algorithm, extended version
Raft protocol, Figure 2, safety and Figure 8, membership, snapshots, and client interaction. Primary protocol reference.
Lamport: Time, Clocks, and the Ordering of Events in a Distributed System, 1978
Happened-before, logical clocks, and the distinction between partial and total ordering.

Lesson browser Distributed consensus, replication, and fault tolerance lessons Previous: Paxos and preserving an earlier decision Next: Retries and the boundary of exactly once