Distributed consensus, replication, and fault tolerance / personal lessonsLesson 2 of 17
Distributed systems · Lesson 2

Failures, timeouts, and missing information

Explain why silence does not distinguish a crash from a delayed message.

By the end: Enumerate plausible outcomes of a timed-out operation without pretending to know which occurred.

Observe messages, not remote reality

A sends a request to B and waits. Silence is compatible with a lost request, a slow B, a crashed B, a completed operation with a lost response, or a partition that blocks communication in one or both directions. A timeout means A’s waiting policy expired. It is not evidence that B performed no work.

Imagine two worlds that deliver exactly the same messages to A up to the timeout. In one, B crashed before doing anything. In the other, B completed the operation but its response is delayed. A has the same local evidence in both worlds. No local computation can reliably distinguish them at that moment. This indistinguishability argument will explain both safe retry rules and limits on consensus.

Separate the operation outcome from the waiting outcome

A request usually crosses several distinct boundaries before a client sees a result. The client prepares a message, a transport sends it, the server receives it, the server decides whether to execute it, and a response travels back. Some of these steps may happen despite the client's inability to observe them. A local send completing does not generally prove that the remote application executed the command. Even a transport acknowledgment need not say that application data reached durable storage. The interpretation depends on which component sent the acknowledgment and what that component promises.

Use a paper example involving an image-processing job. At local time zero, a client requests creation of job J. Its deadline expires after three seconds. In one execution the request never arrives, so no job exists. In another, the server durably creates J after one second, but the reply is lost. In a third, the request waits in a queue until the fourth second and then creates J after the client has stopped waiting. All three executions can produce the same visible client history through the deadline. A timeout cannot distinguish absent, completed, and still-pending remote work.

Cancellation adds another message rather than erasing these possibilities. Suppose the client sends Cancel J after timing out. That message can be delayed, lost, or processed after J finishes. A server may define cancellation as a conditional transition that succeeds only while the job is pending. A successful cancellation response then has meaning under that contract. Merely closing a connection or asking to cancel does not prove the server rolled back work. For irreversible actions, such as sending an email, a completed effect may have no literal inverse even if the application later records a cancellation.

The two-world reasoning in the opening section concerns knowledge, not equal likelihood. The lost-request world and lost-response world need not be equally common. A monitoring system may provide evidence that makes one more plausible. But if the correctness of an action requires knowing that no earlier effect occurred, a probability estimate does not supply that fact. A duplicate submission can be unsafe even when duplicate processing is rare. Choose a response to uncertainty that remains correct in every execution admitted by the contract, rather than silently assuming the most common execution occurred.

One possible status operation asks about J using its original identity. That helps only if the server defines how status relates to pending requests. A response saying unknown might mean no record currently exists, while an old delayed submission can still arrive later. Treating unknown as permission to create unrelated replacement work needs additional rules. The later retry lesson explains durable deduplication and identity retention. Here the necessary first step is to list the remote events that remain possible after each local observation, including events that may occur after the timeout.

Choose a timing model

A synchronous model assumes known bounds on relevant processing and message delays. A fully asynchronous model has no such bounds; this does not mean all messages are permanently lost. In common partial-synchrony models, useful bounds hold eventually, or exist without being known in advance. A practical protocol can preserve safety during arbitrary delays while needing a sufficiently stable period to make progress.

A heartbeat is a recurring message used to suspect failure when arrivals stop. Short timeouts detect actual failures sooner but produce more false suspicions during pauses. Long timeouts reduce false suspicions but delay recovery. Randomized election timers can reduce repeated collisions; they cannot prove that a silent peer has died. A failure detector is a mechanism that supplies suspicions or information about failures, with guarantees determined by its assumptions.

Identify which bound makes a timeout informative

A known delay bound is a statement about an entire relevant path, not simply a typical network round trip. If a healthy server can pause without a known limit, bounded wire transmission alone does not imply bounded response time. Queueing, processing, storage, and return transmission may all contribute. A timeout can rule out a healthy execution only when its threshold exceeds the applicable bound and the assumptions behind that bound actually hold. Otherwise it establishes suspicion rather than proof of a crash. Even a correct suspicion of failure may leave an earlier operation's outcome unknown.

Take a constructed synchronous example. Assume a request reaches a healthy server within 40 milliseconds, the server finishes its required work within 30 milliseconds, and its reply reaches the caller within another 40 milliseconds. Allowing a suitable margin for the caller's timer, a response is expected within 110 milliseconds under those assumptions. Silence beyond that bound says at least one assumption failed. It does not uniquely identify which one. The server may have crashed, a link may have violated its bound, or storage may have stalled beyond the promised processing time. These are illustrative limits, not measurements or recommended settings.

Contrast a fully asynchronous model. Messages to functioning participants can take arbitrarily long while still eventually arriving. A timer expiration cannot exclude the execution where the next useful reply arrives just afterward. This model is useful for separating safety from timing assumptions; it does not claim that practical networks always behave with unlimited delay. Nor does it automatically permit every message to vanish forever. Later, the consensus impossibility lesson uses reliable delivery with unbounded delay to explain why deterministic termination cannot be guaranteed in every admissible execution with a possible crash.

Partial synchrony supplies a different progress argument. Imagine that a network suffers an interval of long unpredictable delays, then begins delivering messages within a stable useful bound. Before stabilization, a protocol may repeatedly suspect healthy leaders and fail to finish requests. After stabilization, appropriately chosen or adapted timeouts can allow one leader to remain in place long enough to finish. The protocol should not corrupt decisions during the earlier interval. Safety must follow from its message and storage rules, while progress may depend on the eventual timing conditions. Merely lengthening a timeout does not establish those conditions.

Heartbeats have direction and scheduling costs too. A follower missing heartbeats may be unable to receive from a healthy leader, while the leader still receives traffic from that follower. Alternatively, a paused follower may fail to process messages already waiting in its network buffers. Both can trigger the same suspicion. Randomizing election delays helps competing candidates avoid repeatedly starting together, but a random timer does not inspect remote reality. Election rules must ensure that a mistaken suspicion does not by itself authorize incompatible decisions.

Work through the model

WorldB’s actual actionA’s observation at timeout
Request lostNo operationNo response
Response lostOperation completedNo response
B pausedOperation not completed yetNo response
The same observation at A supports several incompatible histories at B.

Reconstruct hidden events without choosing one prematurely

The evidence table groups several remote histories under one client observation. Treat each row as a separate possible execution. In the request-lost row, the operation has no server-side effect. In the response-lost row, the effect already exists. In the paused-server row, the effect has not happened yet, but might happen after the pause ends. Nothing in the table assigns probabilities or specifies a retry implementation. Its purpose is to prevent an inference from silence to a unique server history.

Extend the table on paper by giving the request four named events: send, receive, durable completion, and response receipt. The client knows send occurred and response receipt has not occurred by its deadline. It does not know whether receive or durable completion occurred. Now add a server log recording receive. That evidence excludes loss before receipt, assuming the log entry is authentic and belongs to this request. It still does not prove durable completion. A log saying started can survive alongside a failed operation; a log buffered in memory may disappear during the very crash being investigated.

Next suppose a trustworthy recovered record says J completed durably before the server crashed. That rules out no-effect histories under the stated durability contract. The client timeout remains an accurate report about waiting, but no longer leaves the investigator uncertain about whether J completed. This illustrates why evidence is relative to the observer. The server, a recovered server, and the original client need not know the same facts at the same moment. A protocol cannot act on an investigator's later global reconstruction until the relevant information reaches its participants.

Explore an asymmetric connection as another separate case. A's submission reaches B, and B stores J. Every reply traveling from B to A is dropped. Repeated submissions from A may all arrive despite repeated timeouts. Calling this simply a disconnected pair hides the direction that matters. If submissions trigger fresh work each time, the service can accumulate many jobs while A believes it has made no progress. Stable request identity and server-side rules can address duplication, but the network itself has not prevented repeated delivery. Healing only the return direction may suddenly reveal work that was already complete.

For an incident timeline, retain the original client deadline, request identity, server receipt evidence, storage evidence, and any later response. Do not sort unsynchronized machine timestamps and assume that their numerical order proves event order. The next lesson builds order from local execution and actual messages. For this lesson's table, the complete explanation is available without playback or controls. These are bounded reasoning cases rather than a tool that can discover which hidden history occurred on a real network.

Durability and independent failures

A crash-stop model says a failed process never returns. Crash-recovery allows restart, so persistent state matters. If a server acknowledges a vote or a log entry and later forgets it, a proof that relies on that memory no longer applies. Durable means the acknowledged record survives the failures covered by the storage contract. A write into a language buffer is not automatically a durable disk write.

Partitions can be asymmetric. B receiving A’s message does not guarantee A can receive B’s reply. Even when each machine has a high uptime, common power, network, software, or operator failures can defeat an independence assumption. Do not multiply independent-failure probabilities until you have justified independence. Later lessons distinguish recovery from one failed machine, losing a majority, and losing the stored history itself.

Make crash recovery preserve previous obligations

Crash recovery creates a second uncertainty boundary inside a server. A process may have changed memory, asked the operating system to write a file, received a storage acknowledgment, or completed a durable record. These milestones are not interchangeable. The server must specify which completed storage operation survives which failures. A process crash, an operating-system crash, loss of power, and physical destruction of a device can have different consequences. Calling data persistent without naming the covered failure makes it impossible to decide whether an early response was justified.

Consider a paper server that grants an exclusive assignment until its owner releases it. It receives a request, records the assignment only in memory, and replies that the assignment is final. After a process restart, memory is empty. If it now grants the same exclusive assignment to someone else, it can contradict its earlier response even though it never lied while running. A crash-recovery protocol must restore the obligation or refuse to act until it can recover sufficient evidence. Later election lessons use durable votes as a concrete protocol obligation. Persistence matters because old decisions constrain future behavior.

Now change the example so the assignment record reaches durable storage, but the server crashes before replying. Recovery can preserve the assignment, yet the client still lacks confirmation. Durability solves loss of server memory, not loss of client knowledge. If the recovered service processes a retry, it must relate that retry to the existing assignment under an explicit identity contract. Retrying with a new identity or rebuilding only visible application fields can lose that relationship. The retry and snapshot lessons will explain why the result record may be part of the durable application state too.

Failure independence is another assumption to inspect rather than infer from replica count. Suppose two machines each have a small chance of stopping during a chosen interval. Multiplying those probabilities estimates simultaneous failure only if the relevant events are independent. A shared power failure can stop both at once, and a shared deployment can introduce the same defect everywhere. Adding machines within the same failure domain may improve tolerance of isolated hardware faults without changing tolerance of that common event. Conversely, spreading machines geographically changes communication paths and can introduce longer or more variable delays.

Keep failure conclusions narrow. Observing a process restart does not prove its disk lost data. Observing intact disk files does not prove a complete recoverable protocol state. Observing every process running does not prove that the required participants can communicate or respond before deadlines. For each proposed recovery action, identify which earlier promise it must preserve and which evidence survives to support it. If that evidence is unavailable, waiting can protect safety while reducing progress. Restoring service by discarding uncertainty is a policy change, not proof that the uncertain operation never happened.

Exercises

Did the charge happen?

A payment request times out after two seconds. Can the client safely issue a new charge with a new identity?

Hint

Compare request loss and response loss.

Worked answer
Hidden historyNew charge identityPossible result
First request lostProcessed onceOne charge
First charge completedProcessed againTwo charges
The client cannot choose a correct action by assuming only the first world exists.

Not merely because of the timeout. In the response-loss world the new identity can cause a second charge. Reuse an operation identity under a documented deduplication contract, or query the original operation’s status. A timeout is an unknown outcome, not a confirmed rejection.

Tune a timeout

A 200 ms timeout frequently expires during 500 ms process pauses. Would increasing it prove future suspicions correct?

Hint

A threshold changes policy, not the evidence in a silent interval.

Worked answer
Timeout500 ms pauseCrash detection
200 msFalse suspicion likelyEarlier suspicion
1 secondThis pause fitsLater suspicion
These durations are invented policy examples, not recommended production defaults.

No. It would reduce false suspicions for those particular pauses and delay detection of real crashes. Longer or unbounded pauses can still exceed it. Safety must not depend on the assumption that every expired timeout identifies a dead process.

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.