Course contents
On this page
Distributed failure models — extended reference
Original detailed coverage and citations accompanying the focused distributed failure models lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 5: Correctness across machines
Prerequisites: Lesson 24 and the preceding foundations.
Learning outcomes
- Reason about delayed, duplicated, reordered, and lost messages without assuming a timeout proves failure.
- Separate physical clocks, causal order, and protocol epochs.
- Design a retry outcome that remains valid after a client or server loses its reply state.
A silent machine is not necessarily a failed machine
A leader stops responding for 200 milliseconds. Another node’s failure detector suspects it after 150 milliseconds and begins replacement. The original process was paused, not dead. It resumes with stale information and attempts to continue writing. A distributed engine must prevent obsolete authority from corrupting the new state.
The central difficulty is partial failure. One participant can be alive while another cannot reach it. Messages can be delayed, duplicated through retries, or delivered after a deadline. A local durable transaction does not tell another machine what happened unless a protocol communicates and interprets that outcome safely.
Failure models and assumptions
A crash-stop model assumes a failed process never returns. A crash-recovery model allows it to restart, possibly with durable state but without volatile memory. Network partitions prevent selected communication while processes continue running. Byzantine models allow arbitrary or malicious behavior and require different protocols.
Most ordinary database architecture discussions assume crash and communication failures rather than arbitrary malicious replicas. That assumption should be explicit. Transport authentication helps reject unauthorized participants, but it does not transform a crash-fault protocol into a Byzantine-fault-tolerant one.
Timing assumptions also matter. In a fully asynchronous model, there is no fixed bound that distinguishes a failed participant from a sufficiently delayed one. Practical systems use timeouts to make progress under expected conditions. Safety must not depend on a timeout being a perfect proof of death.
Failure detection is suspicion
A heartbeat detector tracks recent communication and suspects failure when expected messages do not arrive. Short thresholds detect real failures quickly but create more false suspicions during pauses or congestion. Long thresholds reduce false suspicions while extending failover delay.
For an illustrative 200-millisecond pause and a 150-millisecond threshold, a healthy process can be suspected before it resumes. The correct response is not to assume such pauses never happen. The leadership and storage protocol must reject stale work even when old processes return.
Randomized election timers can reduce synchronized collisions in some consensus protocols. They do not provide authority by themselves. A winner must satisfy the protocol’s durable voting and log rules. An operational dashboard should distinguish detector suspicion, election, leadership establishment, and useful service restoration.
Clocks and ordering
Wall clocks estimate physical time and can drift, step, or be corrected. Monotonic clocks support elapsed-duration measurement under their platform semantics. Logical clocks represent ordering relationships without claiming exact physical time. A distributed design should state which kind of clock each mechanism uses.
Lamport’s happens-before relation captures causal ordering: events in one process are ordered, and sending a message precedes receiving it. Logical timestamps can respect that relation, but a smaller timestamp does not imply every event is causally related. Two independent events can be concurrent in the causal sense even if their numeric timestamps differ.
A wall-clock timestamp from one machine should not casually resolve a strict ownership conflict on another. A clock that is far ahead can make its writes appear newer under a last-write-wins policy. Such policies are valid only when their conflict semantics match the application and their operational assumptions are understood.
Requests have uncertain outcomes
A coordinator can time out while a participant has already committed. A client can retry through a different gateway. A leader can fail after replication but before replying. The protocol must retain enough identity and status to distinguish a duplicate action from a new one.
request sent
-> may not arrive
-> may arrive but not execute
-> may execute but abort
-> may commit but reply disappear
-> may reply while client has stopped waitingThe diagram lists possibilities rather than a sequence every request traverses. A local timeout does not reveal which branch occurred. Safe retries require idempotency, status lookup, or a higher-level protocol that resolves the outcome.
Deduplication records need durable scope and retention. A record stored only in the failed leader’s memory cannot protect retries after leadership moves. A deduplication key reused for a different payload needs rejection. A retention policy shorter than the retry horizon can recreate duplicates after old records are collected.
Epochs and fencing
An epoch or term identifies a generation of authority. A participant includes it in requests, and authoritative receivers reject obsolete generations according to the protocol. This prevents a resumed old leader from acting merely because it still has a live process and credentials.
Fencing must occur at the resource that can be damaged. If two leaders can both write to an external object store or device, a local flag in the new leader is insufficient. The recipient needs a way to validate the fencing token or the architecture needs another safe exclusion mechanism.
Leases can grant authority for a bounded interval under clock and timing assumptions. They can make reads or ownership checks cheaper, but their correctness depends on how expiry and clock uncertainty are handled. A lease should not be described as “a lock with a timeout” without examining old-holder behavior and the validity of the expiry judgment.
Membership and discovery
A cluster needs to know which participants exist and which configuration determines authority. Gossip can disseminate observations and membership information, while consensus may determine an authoritative configuration for safety-critical decisions. Fast dissemination and authoritative agreement solve different problems.
Changing membership changes quorum relationships. Replacing several nodes independently without a safe transition can create disjoint groups each believing it has a majority. The protocol needs an explicit configuration-change procedure. Operational automation must follow that procedure rather than treating machine replacement as a simple address edit.
Discovery also interacts with clients. A stale client may contact an old leader and need redirection. A reachable proxy may cache an obsolete route. Redirect loops should be bounded, and requests should retain operation identity across rerouting. The connection protocol and cluster protocol must cooperate.
Correlated failures and operational reality
Replicas on different virtual machines can still share a rack, power source, network device, storage service, software defect, or administrative action. Counting copies without examining failure domains overstates resilience. A rolling upgrade can create a correlated protocol failure even when hardware is independent.
Pauses and overload can resemble failures. A node performing heavy compaction may miss heartbeats; replacing it can trigger expensive catch-up and worsen cluster load. Failure detection should not become an uncontrolled feedback loop that turns temporary pressure into repeated reconfiguration.
Observability should record authority changes, durable positions, request outcomes, and resource state together. A timeout count alone cannot distinguish a network issue from storage backlog or a stalled scheduler. Fault injection can test the difference, but the design must first define the expected invariant under each fault.
A delayed packet survives a change of authority
Let node A hold authority generation 7 and send a storage write. The network delays that packet. The cluster establishes generation 8 under its coordination protocol and grants authority to B. B writes a new value. The delayed packet from A then arrives. If the storage recipient checks only a valid credential, it can accept A’s obsolete write and overwrite B’s result.
A fencing token solves this only if the recipient enforces it. The resource stores its highest accepted generation and rejects lower generations. Tokens must originate from an authority capable of issuing a meaningful monotonic order, and the recipient’s remembered fence must survive the failures covered by the design. A local counter reset at restart does not provide that property.
apply_write(request):
authenticate_sender(request)
validate_token_provenance_through_authority_protocol(request)
enter serialized durable resource transaction:
if request.generation < persisted_highest_generation:
abort transaction; return STALE_AUTHORITY
persisted_highest_generation = max(persisted_highest_generation,
request.generation)
apply_protected_effect(request)
durably commit fence and effect together
return ACCEPTEDThe fence comparison, monotonic fence advance, and protected effect are one serialized durable operation. Validating provenance beforehand cannot replace the atomic recheck: otherwise an old generation could pass a check, pause while a new generation commits, and then overwrite its effect. This is a conceptual resource interface, not a complete leader-election algorithm. Merely accepting any larger number supplied by a caller would allow stale or unauthorized clients to invent authority. The token’s provenance, the persistence boundary, and the ordering of effects all matter. Fencing turns the question from “is the old process dead?” into “can its requests still change this resource?”
A resource that cannot validate fences may require a different architecture. For example, access can be mediated through a service that does enforce authority, or a storage protocol can provide exclusive ownership with documented guarantees. Deleting an old process from a service registry does not retract packets already sent or invalidate credentials it still holds.
Separate safety from progress
A protocol is safe if it never accepts an invalid history under its assumptions. It is live if it eventually makes progress under its timing and failure assumptions. During a network partition, a majority-based protocol can preserve safety while a minority cannot complete writes. This is not a failure of the safety argument; it is the chosen availability behavior.
A timeout can trigger a new election without proving a process crashed. Safety comes from voting and log rules that prevent incompatible committed histories. Liveness depends on communication and scheduling eventually being good enough for one election to succeed. Continual false suspicions can preserve safety while destroying useful availability.
This separation also helps operational diagnosis. Repeated elections with no divergent accepted data indicate a progress problem. Two leaders accepting incompatible committed writes indicate a safety failure. The remedies differ: tuning timeouts may improve progress but cannot repair a protocol that lacks durable authority or conflict rejection.
Progress guarantees always include assumptions. If a storage device never completes a flush, a network never delivers any packet, or every candidate is paused before election completion, an ordinary crash-fault database cannot promise bounded completion. A production SLO describes expected behavior in an operating envelope, while a protocol proof states which failures preserve correctness.
Time measurement can fail in subtle ways
Use a monotonic clock for local elapsed deadlines where supported. A wall clock corrected backward can make a timeout last longer than intended; a forward correction can expire it immediately. Monotonic clocks have platform-specific behavior around suspension and restart, so absolute stored deadlines need a separate interpretation when a process restarts on another machine.
Suppose the client allows a total of 300 milliseconds. A gateway spends 80 milliseconds before forwarding, but the server independently starts another 300-millisecond budget. A downstream service starts a third. The overall operation can exceed the client’s limit substantially. Propagating remaining budgets and recording time spent helps align cancellation, but clock comparisons across hosts still require care.
An absolute deadline can be convenient when clocks are bounded and trustworthy enough for the use. A duration budget avoids direct cross-host timestamp comparison but must account for time already consumed and messages delayed in transit. Neither representation proves that cancelling a request reverses a committed action. Deadline expiration limits waiting; transaction outcome remains a separate state.
Logical clocks order causally related events without giving elapsed durations. If A sends a message and B receives it, B advances its logical clock beyond the received value. Two unrelated events can still receive ordered scalar timestamps. Therefore timestamp(A) < timestamp(B) does not imply A caused B. Vector clocks carry more dependency information at greater metadata cost, while hybrid approaches serve other engineering needs.
Model uncertainty as a state instead of a generic error
A client operation can be known rejected before execution, known committed, known aborted, or unresolved from the client’s perspective. These states affect safe behavior. A malformed request rejected before admission can be corrected and resubmitted. A connection reset after a commit attempt requires outcome resolution or idempotent retry with the same identity.
An operation-status API can expose accepted results by identity, but its own consistency matters. Querying a stale replica and receiving “not found” does not prove the operation never committed. The status lookup needs an authority or a documented wait condition sufficient to distinguish absence from lag. Otherwise it simply moves the ambiguity into a second API.
Deduplication storage must be atomic with the business effect. Recording a key first and crashing before the effect can suppress a valid retry. Applying the effect first and recording the key later can duplicate it. A transaction containing both the result and effect gives one local solution; external consequences need their own idempotency or reconciliation boundary.
Retention is part of semantics. If clients may retry for twenty-four hours but deduplication keys expire after one hour, a delayed retry can execute again. A service can reject old identities after expiration instead of treating them as new. That policy should be visible so callers do not interpret silent reexecution as a guaranteed exactly-once result.
Message delivery and operation execution are different layers
TCP provides an ordered byte stream while a connection remains meaningful, but application reconnects can resend requests. A message broker may redeliver after acknowledgment uncertainty. A database may rerun a transaction callback after validation failure. Each layer can create repeated processing even if the transport itself does not duplicate delivered bytes within one stream.
At-most-once delivery can lose an action. At-least-once delivery needs safe duplicates. Exactly-once effects within a defined transactional boundary can be achieved by durable identity and atomic application, but that does not create a universal guarantee across arbitrary external services. The scope and retention assumptions must accompany the phrase.
Ordering has similar boundaries. Two messages on one stream have an order; messages on separate connections need another mechanism if their relative order matters. A reconnecting client may observe results in a different arrival order from the server’s commit order. Sequence numbers and version checks can prevent stale updates from overwriting newer local state, provided the sequence’s scope is explicit.
For inventory, a client can send operation 105 and 106 concurrently but still require one authoritative item history. The server can order them by its transaction protocol rather than client arrival timestamps. The client UI then reconciles against authoritative versions instead of assuming that the last response received represents the newest state.
Correlated failures change replica arithmetic
Three replicas placed on three machines may tolerate some machine failures. If all three depend on one storage array or one network path, that shared dependency can remove every copy at once. A rack, zone, region, credential, or deployment automation system is a possible failure domain. Independence must be established for the failures the product promises to tolerate.
Software changes can be correlated failures even with geographically separate hardware. A new parser bug can crash every replica on the same input. A faulty migration can delete data everywhere. Independent backups and staged rollout reduce different risks than quorum replication. Counting live copies cannot answer all recovery questions.
An overload event can create an operational feedback loop. A lagging replica misses heartbeats; replacement starts a full copy; the copy saturates storage or network; other replicas fall behind and are replaced. Automation should distinguish temporary overload, a process pause, and permanent loss sufficiently to avoid uncontrolled churn. Safe protocol behavior alone does not guarantee stable recovery behavior.
Capacity should reserve headroom for catch-up and reconfiguration. A cluster that barely meets steady-state demand may become unavailable after losing one node even when it remains logically capable of forming a quorum. Failure tolerance has a resource dimension as well as a vote-count dimension.
Build a fault model with observable outcomes
For a regional partition, specify which side can accept writes, whether reads can be stale, and how rejected requests are reported. For a paused old leader, specify fencing and retry handling. For disk corruption, specify detection and recovery rather than assuming replication automatically repairs every byte. Each fault should map to permitted externally visible histories.
Telemetry should join operation identity, leadership generation, durable position, applied position, and timing spans. A timeout trace without those fields cannot tell whether the operation was never admitted, queued, committed, or merely unable to send its reply. The goal is enough evidence to resolve uncertainty without exposing private data in logs.
This approach makes distributed complexity teachable: uncertainty is represented, authority is explicit, and each optimization states its assumptions. The system can then use timeouts and retries to improve progress while durable protocol rules preserve safety when those guesses are wrong.
The same observation has two explanations
Case A: actual failure
new node -> heartbeat request -> old node [crashed]
new node -> timeout -> establish replacement through authority protocol
Case B: delayed network or scheduler
new node -> heartbeat request ....... delayed ....... old node [alive]
new node -> timeout -> establish replacement through authority protocol
old node resumes -> stale-generation write -> resource rejectsBoth cases produce the same missing-response observation before the timeout. A detector cannot know which world it occupies from that observation alone. The authority protocol must remain safe in both. Fencing is needed because Case B allows the old process and its delayed requests to return after replacement.
An observer may obtain stronger evidence later, such as a powered-off host or an explicit shutdown acknowledgment. That evidence can improve operational confidence, but a distributed safety protocol should not require an infallible human diagnosis for ordinary failover. The useful invariant is that incompatible generations cannot both produce accepted authoritative effects.
Lease expiry needs an explicit pause model
Suppose an old holder believes its lease ends at local time L. It pauses before checking the clock, resumes much later, and sends a write based on a cached “lease valid” flag. The lease duration did not make that action safe. The holder must validate authority at the relevant point, and the resource may still need fencing to reject an already delayed write.
A bounded-clock-drift lease protocol can coordinate intervals conservatively so new authority is not granted while old authority may still act under the assumptions. Process pauses, message delay, and clock behavior affect where expiry is checked and how the interval is interpreted. A lease implementation should state these assumptions instead of relying on an optimistic wall-clock comparison.
A database can use leases for efficient reads while relying on a replicated log for writes. The read optimization then depends on both lease validity and applied state. A valid lease over an out-of-date state does not make a current read correct. Authority and freshness remain independent evidence requirements.
Interpret errors without losing the operation
A useful client-facing result distinguishes a request rejected before acceptance from a result whose outcome is unknown. The latter should preserve the operation identifier so a retry or status check resolves the same intended action. Generating a new identifier after every timeout converts uncertainty into a potential duplicate.
A retry through a newly discovered leader should carry the same payload hash or equivalent binding. If the identity is reused with a different amount or item, the server should reject the mismatch rather than return an unrelated cached result. This protects both correctness and user understanding when application code accidentally reuses identifiers.
The status-retention policy closes the final gap. An expired operation identity can produce an explicit “too old to resolve safely” response rather than silently execute again. That response is less convenient than a perfect remembered result, but it is a truthful boundary. Representing uncertainty accurately is a better foundation for low-latency infrastructure than hiding it behind generic retries.
Case connection and design conclusion
Lamport’s work supplies the foundational ordering vocabulary. Raft provides a concrete protocol that treats delayed messages and leadership generations explicitly. These sources teach why distributed correctness requires more than copying data and waiting for heartbeats.
The engineer’s first distributed artifact should be a failure model and an authority model. State which failures are tolerated, which observations are uncertain, who may make a decision, and how stale authority is rejected. Lesson 26 then defines the observable consistency contracts those protocols are intended to provide.