1.1 Distributed System Model: Partial Failures, Timing, and the Impossibility Boundary
In the common message-passing model, distributed nodes exchange messages and can fail independently. Whether network and processing delays have upper bounds is part of the system model. One smooth load test is insufficient evidence of a permanent bound. Correctness claims depend on these assumptions.
Partial Failure Leaves Outcomes Unknown
After a client calls a remote service and times out, there are at least several possible causes:
- The request never reached the server;
- The request arrived and the server is still processing it;
- The business operation committed, and the response was lost in transit;
- Overload on the server, network, or client side;
- The request is still in queue and will be processed later.
A timeout alone cannot establish that the business operation failed: the observer did not receive a result before the deadline. Retrying a write may produce a second side effect.
Suppose debit op-17 committed but its response was lost. Retrying with a new request ID may debit the account again. Reusing the same idempotency key lets the server recognize the duplicate if it durably stores the key together with the debit result. That record must commit atomically with the debit; otherwise, a crash between the two steps leaves a gap. Status queries and reconciliation recover outcomes. A longer timeout mostly adds waiting.
First, declare the system model
Synchronous Model
Message delivery and process execution rates obey known timing bounds. Protocols that use physical clocks must also state their clock-error assumptions. Ordinary networks struggle to maintain strict bounds indefinitely.
Asynchronous Model
There are no assumed upper bounds on message or processing delays. A period of silence alone cannot distinguish a crashed node from a slow node or network.
Partially Synchronous Model
One common definition assumes that specified bounds on message and processing delays hold after an unknown time. Another allows the bounds to hold throughout execution while remaining unknown to the protocol. Engineering consensus systems in the Raft and Paxos families typically need sufficiently stable, timely communication and processing to make progress. This is a timing assumption, unrelated to eventual consistency.
The model should also declare fault types:
- crash-stop: nodes that crash never come back;
- crash-recovery: nodes can recover with persistent state;
- omission: a message might be lost;
- Byzantine: Nodes may send arbitrary or malicious information.
Protocols that can only tolerate crashes are unable to automatically defend against silent disk failures, certificate leaks, or malicious nodes.
Separate Safety from Liveness
- Safety: Bad things never happen, for example, the same log location never commits two different values;
- Liveness: Under the stated conditions, good things eventually happen. For example, new writes eventually commit after enough replicas recover communication and processing.
During a network partition, a consensus system may stop writing to preserve safety, temporarily losing liveness. In a three-replica majority protocol, one healthy replica cannot form a majority even if its own network works. Testing "eventual recovery" does not substitute for proving "no conflicting commits."
CAP discusses response selection during partitioning
In CAP:
- Consistency refers to linearizability semantics;
- Availability requires every request reaching a non-failed node to eventually return a result allowed by the operation specification. Answering every register read or write with "service unavailable" does not qualify, and the definition sets no millisecond latency target;
- Partition tolerance includes sustained message loss between nodes in the failure model and asks which guarantees the system can retain under those conditions.
Suppose register x starts at 0, and replicas A and B cannot communicate. A accepts write(x, 1) and returns success. Only afterward does a client read from B. Linearizability requires 1, but B cannot even know whether A received that write. Waiting or refusing service loses the availability guarantee; returning the old value 0 violates linearizability. Guessing a new value fails in the alternative execution where no write occurred.
This is the CAP conflict: during such a partition, a read/write service cannot guarantee both linearizability and completion of requests at every non-failed node.
Real systems don't permanently label themselves as "CP" or "AP." The same product can reject metadata writes and return stale values on cache reads; even without network partitions, trade-offs remain between latency, fault recovery, and consistency levels.
CAP cannot replace transaction isolation, durability, causal consistency, and latency design.
FLP Limits Guaranteed Termination for Deterministic Consensus
FLP proves that in a fully asynchronous message-passing system, even with reliable message delivery and at most one possible process crash, no deterministic consensus algorithm can guarantee agreement, validity, and termination in every admissible execution. Permanent network partitions are unnecessary; arbitrarily long but finite delays already create the difficulty.
It does not say that practical systems can never reach consensus. Timeouts and leader elections alone do not bypass FLP; a progress guarantee needs additional assumptions such as eventual timeliness or a stronger failure detector. Randomized algorithms change the form of the guarantee, for example to termination with probability 1 under the relevant model. Engineering consensus protocols usually preserve safety during unfavorable timing and resume progress when conditions recover.
A failure detector can only suspect
Heartbeat timeout means "unreachable under current threshold and observation point," not that the node has died. A too-short threshold causes false failures and frequent leader elections, while a too-long threshold delays recovery.
Fault detection must also consider:
- Stop-the-world GC or CPU starvation;
- Network one-way interruption;
- Long process pauses or VM migration;
- Switch and DNS local outages;
- The node provides health checks but can't access the critical disk.
Design documents should state assumptions
- Does the system retain persistent state after a node failure?
- Could the network potentially partition, reorder, duplicate, or delay messages?
- What does the protocol tolerate in terms of node failures, and why?
- Which safety properties must always hold, and what progress must eventually occur under the stated conditions?
- When the result of a request is unknown, how can the caller query or retry?
- Is time and order derived from physical clocks, logical clocks, or log positions?
The next lesson specifically addresses the final question: how distributed systems express event ordering, and what exactly each consistency model promises.
References
Dwork, Lynch, Stockmeyer, Consensus in the Presence of Partial Synchrony
Fischer, Lynch, Paterson, Impossibility of Distributed Consensus with One Faulty Process
Gilbert, Lynch, Perspectives on the CAP Theorem