On this page

System Models, Failure Models & Correctness

Every distributed algorithm comes with fine print. Raft is "correct" — but only if a node that crashes stops sending messages instead of sending garbage. Paxos is "safe" — but only if acceptors do not forget what they promised after a reboot. A heartbeat failure detector "works" — but only if a slow node and a dead node are eventually distinguishable. That fine print is called the system model: a precise statement of what the environment may and may not do to your algorithm.

This page is about that fine print. It is the lens through which every other page in this section should be read. When you see a theorem like FLP ("consensus is impossible") or a protocol like Paxos ("consensus is possible"), the two are not contradicting each other — they are answering the question under different system models. Learn to read the model first, and most apparent paradoxes in distributed systems dissolve.

We will cover:

  1. What a system model is and why you cannot avoid having one
  2. Timing models — synchronous, asynchronous, partially synchronous
  3. Process failure models — crash-stop, crash-recovery, omission, timing, Byzantine
  4. Network failure models — fair-loss, stubborn and reliable links, partitions
  5. The Two Generals problem — the simplest impossibility result, and what it teaches
  6. Correctness as safety and liveness — and why safety is never negotiable
  7. Measures of correctness — linearizability, serializability and friends as properties
  8. Stateless vs stateful services and why state is where all the difficulty lives
  9. How real systems pick a model, and what breaks when reality steps outside it

1. What Is a System Model?

A system model is an abstraction of the environment an algorithm runs in. It answers three questions:

QuestionThe model's answer is calledExample answers
How long can things take?Timing model"Messages arrive within 10 ms" / "no bound at all" / "eventually bounded"
What can a node do wrong?Process failure model"Stop forever" / "stop and restart" / "lie arbitrarily"
What can the network do wrong?Network / link model"Lose messages but not forever" / "never lose anything" / "split in two"

An algorithm is only ever proven correct relative to a model. A proof says: "if the environment behaves within these bounds, then the algorithm guarantees these properties." Outside those bounds, the proof says nothing — not that the algorithm fails, but that you are now on your own.

Why every algorithm assumes one, even if it does not say so

Consider a naive "primary/backup" design that a team might sketch on a whiteboard:

The backup pings the primary every second. If three pings go unanswered, the backup promotes itself.

This design has a system model whether or not anyone wrote it down:

  • Timing: it assumes that a healthy primary always answers within three seconds. That is a synchronous assumption.
  • Process failures: it assumes that a primary which stops answering pings has also stopped serving clients. That is a crash-stop assumption.
  • Network: it assumes that if the backup cannot reach the primary, nobody can. That is an assumption that partitions do not happen (or happen symmetrically).

Each of those assumptions is false in production. A primary in a 5-second garbage-collection pause is alive but silent. A primary whose link to the backup failed but whose link to clients is fine keeps serving writes. The result is two primaries — split brain — and the design never "had a bug" in its code. The bug was in the model.

The habit to build

When you read any protocol, design doc or vendor whitepaper, find the sentences that start with "we assume". If there are none, the assumptions are still there — they are just hidden, which is worse.

Models are a ladder of pessimism

System models are usually arranged from benign to hostile. A more hostile model makes algorithms harder to design and more expensive to run, but an algorithm proven correct in a hostile model is also correct in every gentler one.

flowchart LR
    subgraph Timing["Timing (left = easier for algorithms)"]
        direction LR
        S["Synchronous"] --> PS["Partially synchronous"] --> AS["Asynchronous"]
    end
    subgraph Process["Process failures (left = more benign)"]
        direction LR
        CS["Crash-stop"] --> OM["Omission"] --> CR["Crash-recovery"] --> TF["Timing / performance"] --> BZ["Byzantine"]
    end
    subgraph Network["Links (left = more reliable)"]
        direction LR
        PL["Perfect links"] --> FL["Fair-loss links"] --> PT["Partitions possible"]
    end

The ordering of crash-recovery relative to omission varies between textbooks — what matters is the direction: every step right allows the environment to do more damage.


2. Timing Models

The timing model says what you can assume about how long message delivery and computation take, and about how fast clocks drift relative to each other.

2.1 The synchronous model

In the synchronous model there are known upper bounds:

  • Δ — every message sent between correct processes is delivered within Δ time units
  • Φ — every correct process takes a step within Φ time units (no unbounded pauses)
  • ρ — every local clock drifts from real time by at most ρ

Given these bounds, a silent process is a dead process: if you sent a request and no reply arrives within 2Δ + processing time, the other side has failed. Perfect failure detection is possible.

Consequences:

  • Consensus is solvable even with Byzantine faults (with enough nodes, or with signatures).
  • Algorithms can proceed in lock-step rounds: everyone sends, waits Δ, then computes.
  • Time-based tricks — leases, timeouts, "wait out the uncertainty" — are provably safe.

Where it is (approximately) real: hardware buses, avionics networks such as time-triggered Ethernet, a single rack with real-time OS scheduling. Where it is not real: anything with a garbage collector, a shared cloud network, a virtual machine that can be live-migrated, or a disk that can stall for seconds during a firmware hiccup.

2.2 The asynchronous model

The asynchronous model makes no timing assumptions at all:

  • Messages are eventually delivered (if the link is reliable), but with no bound on delay
  • Processes run at arbitrary, unbounded relative speeds
  • There are no useful clocks

This is the model of maximum humility. Any algorithm proven correct here works no matter how slow or erratic the system becomes.

The price is steep. In the asynchronous model you cannot distinguish a crashed process from a slow one — ever. That single fact drives the FLP impossibility result: no deterministic algorithm can guarantee that consensus terminates if even one process may crash. It also means timeouts are meaningless: any finite timeout can expire on a perfectly healthy process.

What is achievable asynchronously:

  • Reliable broadcast (everyone correct delivers the same set of messages)
  • Causal broadcast (see Causality, Version Vectors & Dotted Version Vectors)
  • Eventually consistent replication and CRDTs
  • Safety of consensus — Paxos and Raft never decide two different values even in fully asynchronous executions; they just might not decide at all

That last bullet is the most important engineering insight in this page, and we will return to it in the safety/liveness section.

2.3 The partially synchronous model

Real networks are not bounded, but they are not adversarial either. Most of the time messages arrive in under a millisecond; occasionally a switch reboots and they take thirty seconds. Dwork, Lynch and Stockmeyer (1988) captured this with partial synchrony. There are two common formulations:

  1. Unknown bound: a bound Δ exists, but the algorithm does not know its value.
  2. Global Stabilization Time (GST): the system may behave asynchronously for an unknown, finite period; after some unknown time GST, all messages arrive within a known Δ.

The GST version is the one most consensus papers use. Read it as: "the network can be arbitrarily bad for a while, but bad periods end."

Consequences:

  • Safety must hold at all times, including before GST — so the algorithm must never rely on timing for correctness.
  • Liveness only needs to hold after GST — so the algorithm may use timeouts to decide when to retry, as long as a wrong timeout can only cause delay, never inconsistency.
  • Timeouts are typically adaptive: if a round fails, double the timeout. Eventually the timeout exceeds the unknown Δ and progress resumes.

This is exactly how Raft, Multi-Paxos, Viewstamped Replication and ZooKeeper's Zab are designed. A Raft follower whose election timeout fires "too early" starts a needless election; that costs latency, but it can never cause two leaders to commit conflicting entries in the same term.

2.4 Comparing the timing models

SynchronousPartially synchronousAsynchronous
Message delay boundKnown ΔExists after GST (or unknown)None
Can detect crashes perfectly?YesEventually (with mistakes before GST)Never
Deterministic consensus with crashesYesYes (needs n ≥ 2f+1)Impossible (FLP)
Byzantine consensusYesYes (needs n ≥ 3f+1)Impossible deterministically
Timeouts can be used for…CorrectnessProgress onlyNothing
Realistic for…Embedded/real-timeDatacenters, the InternetWorst-case reasoning
Example protocolsLock-step round protocolsRaft, Paxos, PBFT, ZabReliable/causal broadcast, CRDTs, randomized consensus (Ben-Or)

Timing assumptions sneak in through clocks

"We don't use timeouts for correctness" is often false in practice because of leases. A leader lease ("I am leader until 12:00:10, nobody else may be") is a synchronous assumption about clock drift. If the lease holder's clock runs slow, or the process pauses past the lease expiry and then continues as if it still holds it, you have two leaders. See Leases & Fencing and Distributed Locking for fencing tokens, the standard defence, and Clock Synchronization for how bad drift really gets.

2.5 A worked example: one protocol, three models

Take the simplest possible task: process A wants to know whether process B is alive. A sends ping, B replies pong.

ModelWhat A may conclude after waiting T and hearing nothing
Synchronous with Δ = 5 ms, T = 10 msB has crashed. This is a fact.
Partially synchronousB is suspected. It may be slow. If A wrongly suspects B, A must not do anything irreversible because of it — and should wait longer next time.
AsynchronousNothing. The pong could arrive in an hour.

The same code — if no reply in T then mark dead — is correct in the first model, a heuristic in the second, and meaningless in the third. The Failure Detectors page formalises this with completeness and accuracy, and shows how φ-accrual detectors turn "suspected" into a continuous suspicion level.


3. Process Failure Models

A process failure model describes how a faulty node may deviate from the algorithm. Each model is a superset of the previous one in what it permits.

3.1 Crash-stop (fail-stop)

The process executes correctly until some point, then halts forever. It sends no more messages, and it never comes back.

  • Easiest model to reason about: a process is either correct or dead.
  • Paxos and Raft are often presented in this model first.
  • Fail-stop sometimes means crash-stop plus perfect detection ("others are reliably notified that it crashed"). Crash-stop without detection is the more common meaning today. Read papers carefully.

Real-world fit: a node whose disk is destroyed and is never brought back with the same identity. Operationally, teams often enforce crash-stop: a replaced node gets a fresh identity and rejoins as a new member, rather than reusing the dead node's ID.

3.2 Crash-recovery

The process may crash and later restart, with some state preserved:

  • State written to stable storage (fsync'd to disk) survives the crash.
  • Volatile state (memory, unflushed buffers) is lost.
  • A process may crash and recover infinitely often, or eventually stay up, or eventually stay down.

This is the model real servers live in, and it is subtler than it looks. Every protocol that tolerates crash-recovery must answer: what exactly must be on disk before I send this message?

ProtocolWhat must be durable before replying
Paxos acceptorThe highest promised ballot and any accepted (ballot, value) — before sending promise or accepted
RaftcurrentTerm, votedFor, and the log entries — before replying to RequestVote or AppendEntries
2PC participantThe PREPARED record — before voting yes
Primary/backup DBThe WAL record — before acknowledging the commit (if the ack claims durability)

Get this wrong and you get amnesia: a node promises something, crashes, recovers without the promise, and promises something contradictory. A Raft node that forgets its votedFor after a reboot can vote twice in the same term, which can elect two leaders in one term — the precise thing Raft's safety proof rules out.

fsync is part of your system model

If you configure a consensus system to skip fsync "for performance", you have silently moved from crash-recovery (which the algorithm was proven for) to a model where recovered nodes may have forgotten acknowledged state. That model has no safety proof. It may work for months, then lose committed data after a power loss across a rack.

3.3 Omission failures

The process stays up but fails to send or receive some messages:

  • Send omission: it thinks it sent a message, but the message never left (full socket buffer, dropped by a local firewall rule)
  • Receive omission: messages reach the machine but are never processed (a full queue that drops on overflow)

Omission failures model "partially broken" nodes: a node whose outbound NIC queue is wedged, or which silently drops requests above a rate limit. From the outside, a send omission is indistinguishable from a lossy link — which is why many textbooks fold omission failures into the network model.

3.4 Timing (performance) failures

The process responds correctly but too late — outside the bounds the synchronous model promised. This is only a "failure" in models that assume bounds; in the asynchronous model, slowness is not a failure at all.

In production, timing failures are the most common kind:

  • Stop-the-world GC pauses (seconds in a large JVM heap)
  • VM steal time, live migration, or a noisy neighbour
  • A disk that stalls on a single fsync for hundreds of milliseconds
  • Swap thrashing, CPU throttling from cgroup limits

Timing failures are dangerous precisely because the node comes back and continues as if no time had passed. A process that checked "my lease is valid" and then paused for 10 seconds will act on that stale check.

3.5 Byzantine (arbitrary) failures

The process may do anything: send conflicting messages to different peers, forge state, collude with other faulty processes, or behave correctly for a while and then lie. The name comes from Lamport, Shostak and Pease's 1982 Byzantine Generals Problem.

Byzantine faults cover both malice (a compromised node) and arbitrary bugs (memory corruption, a bit flip in a message, a software bug that makes a node send a wrong value). The second category matters even inside a trusted datacenter.

The cost: Byzantine agreement in partial synchrony needs n ≥ 3f + 1 replicas to tolerate f faulty ones, versus n ≥ 2f + 1 for crash faults. Protocols like PBFT also need more message rounds and cryptographic authentication. See Byzantine Fault Tolerance and Practical BFT.

3.6 Why 2f+1 and 3f+1? A quorum intuition

The node counts fall out of a simple argument about overlapping majorities.

Crash faults, n = 2f + 1. You must be able to make progress while f nodes are down, so a quorum can be at most n − f = f + 1 nodes. Any two quorums of f + 1 out of 2f + 1 nodes overlap in at least one node, and with crash faults that node is honest — it carries the information from one quorum to the next.

Byzantine faults, n = 3f + 1. A quorum can again be at most n − f = 2f + 1. Two quorums of 2f + 1 out of 3f + 1 overlap in at least f + 1 nodes. Up to f of those may be lying — so at least one honest node is in every overlap. With fewer nodes, the overlap could consist entirely of liars.

f (faults tolerated)Crash: n = 2f+1Byzantine: n = 3f+1
134
257
3710

The same intersection argument powers leaderless replication — see Quorums & Leaderless Replication.

3.7 Summary of process failure models

ModelFaulty process may…Survives restart?Typical toleranceExample systems assuming it
Crash-stopHalt foreverNon ≥ 2f+1 for consensusTextbook Paxos/Raft presentations
Crash-recoveryHalt, then restart from stable storageYes (durable state only)n ≥ 2f+1, plus durable state rulesetcd, ZooKeeper, CockroachDB, Kafka KRaft
OmissionDrop some sends/receivesStays upUsually modelled as link lossRetries, idempotency
TimingRespond lateStays upOnly a failure in synchronous modelsLease-based systems must defend against it
ByzantineAnything, including lyingAnythingn ≥ 3f+1 (partial synchrony)PBFT-family, blockchains

4. Network Failure Models

Processes communicate over links. The link model says what a link may do to messages. The terminology below follows Cachin, Guerraoui and Rodrigues' Introduction to Reliable and Secure Distributed Programming, which builds stronger links out of weaker ones.

A fair-loss link may drop, delay, duplicate and reorder messages, but it is fair:

  • Fair loss: if you send a message infinitely often, it is delivered infinitely often
  • Finite duplication: a message sent a finite number of times is delivered a finite number of times
  • No creation: nothing is delivered that was never sent

This is a reasonable model of raw UDP or IP: any individual packet may vanish, but the network is not systematically eating one specific message forever.

Build on fair-loss by retransmitting forever. If the sender is correct, the message is eventually delivered (indeed, delivered infinitely often). Still no deduplication.

Add deduplication on top of stubborn links:

  • Reliable delivery: if a correct process sends m to a correct process, m is eventually delivered
  • No duplication: m is delivered at most once
  • No creation: as before

TCP gives you something close to this within a single connection. It does not give it across connection resets, process restarts or failovers — which is why application-level idempotency keys still matter. See Exactly-Once Semantics.

The layering is easy to show in code. This sketch builds a perfect link over an unreliable transport using retransmission plus sequence-number deduplication:

// Perfect link built from a fair-loss transport (UDP-like: may drop, duplicate, reorder).
type Packet =
  | { kind: "data"; from: string; seq: number; payload: unknown }
  | { kind: "ack"; from: string; seq: number };

interface FairLossTransport {
  send(to: string, p: Packet): void;           // may silently drop
  onReceive(handler: (p: Packet) => void): void;
}

export class PerfectLink {
  private nextSeq = 0;
  private unacked = new Map<number, { to: string; packet: Packet }>();
  // Per sender: every seq we have already delivered (a real system would
  // compact this into a "delivered up to N" watermark plus a small set).
  private delivered = new Map<string, Set<number>>();

  constructor(
    private readonly self: string,
    private readonly net: FairLossTransport,
    private readonly deliver: (from: string, payload: unknown) => void,
    retransmitMs = 50,
  ) {
    net.onReceive((p) => this.handle(p));
    // Stubborn layer: keep resending anything not yet acknowledged.
    setInterval(() => {
      for (const { to, packet } of this.unacked.values()) net.send(to, packet);
    }, retransmitMs);
  }

  send(to: string, payload: unknown): void {
    const packet: Packet = { kind: "data", from: this.self, seq: this.nextSeq++, payload };
    this.unacked.set(packet.seq, { to, packet });
    this.net.send(to, packet);
  }

  private handle(p: Packet): void {
    if (p.kind === "ack") {
      this.unacked.delete(p.seq);
      return;
    }
    // Always ack, even duplicates — our previous ack may have been lost.
    this.net.send(p.from, { kind: "ack", from: this.self, seq: p.seq });
    const seen = this.delivered.get(p.from) ?? new Set<number>();
    if (seen.has(p.seq)) return;               // no-duplication property
    seen.add(p.seq);
    this.delivered.set(p.from, seen);
    this.deliver(p.from, p.payload);
  }
}

Notice what this code does not survive: if the receiver crashes and restarts, it loses delivered and will deliver duplicates; if the sender crashes, unacked is gone and messages are lost. A perfect link in the crash-recovery model needs both maps on stable storage. The link model and the process model are not independent.

4.4 Partitions

A network partition splits the nodes into groups that can talk internally but not to each other. In link-model terms, a partition is a period during which some links lose every message. If the partition heals, a fair-loss link is still "fair" in the long run; if it never heals, the two sides are effectively separate systems.

Partitions come in shapes that whiteboard designs rarely consider:

flowchart TB
    subgraph Full["Full partition"]
        A1["A"] --- B1["B"]
        C1["C"] --- D1["D"]
        B1 -. "no traffic" .- C1
    end
    subgraph Partial["Partial partition"]
        A2["A"] --- B2["B"]
        B2 --- C2["C"]
        A2 -. "A and C cannot talk, both reach B" .- C2
    end
    subgraph Asym["Asymmetric link"]
        A3["A"] -->|"A to B works"| B3["B"]
        B3 -. "B to A dropped" .-> A3
    end
  • Full partition: the classic CAP scenario. The CAP theorem says that during one, each side must choose between rejecting requests and risking divergence.
  • Partial partition: A and C cannot reach each other, but both reach B. Leader election protocols can flap: A and C each think the other is dead, and B sees both as healthy. Raft's PreVote and CheckQuorum extensions exist largely because of scenarios like this.
  • Asymmetric link: A's heartbeats reach B, but B's replies never reach A. A believes B is dead; B believes A is fine. Failure detectors that only measure one direction get this wrong.

Real partitions also include gray failures: a link that delivers 99% of packets, or delivers them with 2 seconds of latency. These are not partitions in the model's sense, but they trip timeouts like one.

LinkLossDuplicationReorderingBuilt fromReal-world approximation
Fair-lossYes, not systematicFiniteYes—UDP/IP
StubbornEventually deliveredInfiniteYesFair-loss + retransmit"Retry until ack"
Perfect / reliableNever (between correct nodes)NeverPossibleStubborn + dedupTCP within a connection
FIFO perfectNeverNeverNoPerfect + sequence numbersTCP within a connection
Partition-proneTotal loss for a period——Any of the above, brokenEvery real network

5. The Two Generals Problem

The Two Generals problem is the oldest and simplest impossibility result in distributed computing. It was first described by Akkoyunlu, Ekanadham and Huber in 1975, and named and popularised by Jim Gray in 1978.

5.1 The setup

Two armies, led by generals A and B, are camped on opposite hills with an enemy city in the valley between them. They win only if both attack at the same time; if only one attacks, it is destroyed. They can communicate only by sending messengers through the valley, and any messenger may be captured.

General A sends: "Attack at dawn." Should A attack?

  • A does not know whether the messenger arrived. So A waits for a confirmation.
  • B receives the message and sends back: "Agreed, attack at dawn." But B does not know whether the confirmation arrived — if it did not, A will not attack, and B will be destroyed alone. So B waits for a confirmation of the confirmation.
  • A receives the confirmation and sends a confirmation of it. Now A does not know whether that arrived…
sequenceDiagram
    participant A as General A
    participant B as General B
    A->>B: Attack at dawn
    Note right of B: B knows the plan. A does not know B knows.
    B->>A: Ack 1 — agreed
    Note left of A: A knows B knows. B does not know A knows B knows.
    A->>B: Ack 2 — got your ack
    Note right of B: One more level of knowledge — still not common knowledge
    B--xA: Ack 3 — lost in the valley
    Note over A,B: Whoever sent the last message cannot know it arrived

5.2 The proof sketch

Suppose some protocol lets both generals reach a decision with certainty using a finite number of messages. Take the shortest execution in which both decide to attack. Consider the last message in that execution. The sender of that message decides without knowing whether it arrived, so the sender would decide the same way even if it were lost. The receiver, by assumption, decides to attack in the run where it arrived — but what about the run where it was lost?

If the protocol still works when that last message is lost, then the message was unnecessary and there is a shorter successful execution — contradicting "shortest". Repeat the argument and you strip away every message, until you reach an execution with zero messages in which both attack with certainty. That cannot be correct, because with zero messages B has no idea whether A even wants to attack. Contradiction: no finite protocol over a lossy channel achieves certain agreement.

5.3 What it teaches engineers

The Two Generals problem is not about armies. It shows up every time you ask: "did the other side get my message?"

SituationThe Two Generals in disguise
HTTP POST times outDid the server process the payment or not?
A database commit ack is lostIs the transaction committed? The client cannot know.
TCP connection closeFIN/ACK handshakes end with one side uncertain (hence TIME_WAIT)
A message broker ack is lostThe consumer processed the message; the broker re-delivers it

The practical responses are always some combination of:

  1. Accept probabilistic certainty. Send many messengers; the chance that all are captured shrinks exponentially. Retries make success overwhelmingly likely, not certain.
  2. Make actions idempotent. If "attack at dawn" could be safely received twice, A could simply keep sending it. Idempotency keys turn uncertainty about delivery into harmless duplicates.
  3. Make the decision recoverable. Instead of needing both sides to know now, record the decision durably so the uncertain side can ask later. This is what Two-Phase Commit does: a participant that missed the outcome asks the coordinator after recovery.

Two Generals vs Byzantine Generals vs FLP

These three are often confused. Two Generals: honest parties, unreliable messages → certain agreement impossible. Byzantine Generals: reliable messages, lying parties → agreement possible only with n ≥ 3f+1 (without signatures). FLP: reliable messages, honest parties, but one may crash and no timing bounds → deterministic consensus cannot guarantee termination.


6. Correctness: Safety and Liveness

Once you have a model, you need a precise statement of what "correct" means. Leslie Lamport (1977) proposed splitting every correctness requirement into two kinds of property, and Alpern and Schneider (1985) proved that every property of executions is the intersection of a safety property and a liveness property. This split is one of the most useful tools in the field.

6.1 Definitions

Think of an execution as a (possibly infinite) sequence of events.

Safety — "nothing bad ever happens."

  • A safety property is violated at a specific, finite point in an execution. Once it is violated, nothing that happens afterwards can repair it.
  • Equivalently: if an execution violates a safety property, there is a finite prefix that already demonstrates the violation.
  • You can show a safety violation with a finite counterexample — a log excerpt, a trace, a Jepsen history.

Liveness — "something good eventually happens."

  • A liveness property cannot be violated in finite time: any finite prefix can always be extended to satisfy it ("maybe it will happen later").
  • You can never point at a finite log and prove a liveness violation; you can only prove it by showing an execution that runs forever without the good thing.

6.2 Examples

PropertyKindWhy
Two nodes never both believe they are leader in the same termSafetyA violation is a specific moment where both hold that belief
A committed write is never lostSafetyThe loss happens at a specific point
Consensus: all deciding nodes decide the same value (agreement)SafetyTwo different decisions are a finite counterexample
Consensus: the decided value was proposed by someone (validity)SafetyDeciding a never-proposed value is a finite counterexample
Consensus: every correct node eventually decides (termination)Liveness"It hasn't decided yet" can always be followed by a decision
Every request eventually gets a responseLivenessNo finite trace proves it never will
A crashed node is eventually suspected (completeness)Liveness"Eventually"
A correct node is never suspected (strong accuracy)SafetyA false suspicion is a finite counterexample
Replicas eventually converge when writes stopLivenessEventual consistency is a pure liveness property
A request gets a response within 100 msSafety!A bounded deadline makes "too late" observable at a finite time

That last row surprises people. Adding a deadline turns a liveness property into a safety property, because at time 100 ms you can point at the trace and say "it failed." Real SLOs are therefore safety properties of the timed system — but distributed algorithms usually reason about the untimed version.

Notice also that eventual consistency, by itself, has no safety component at all: it permits any value to be read at any time, as long as replicas converge eventually. That is why stronger guarantees such as read-your-writes or causal consistency matter — they add safety. See Consistency Models.

6.3 Why you cannot trade away safety

FLP tells us that in an asynchronous system with one possible crash, a deterministic consensus protocol cannot guarantee both agreement (safety) and termination (liveness). Something has to give. Every practical protocol gives up liveness under bad conditions and keeps safety under all conditions:

  • Paxos and Raft: safe in a fully asynchronous network, live only once the network is stable long enough to elect a leader and complete a round.
  • PBFT: safe always, live after GST.

Why not the other way around? Because the two failures have very different costs:

Liveness failureSafety failure
What the user seesUnavailability, timeouts, errorsWrong answers, lost data, double-spends
Is it visible?Yes — monitoring firesOften silent for weeks
Is it recoverable?Yes — when the network heals, progress resumesOften not — two leaders both committed conflicting writes; there is no "true" history to restore
Who fixes itThe protocol, automaticallyHumans, manually, often with customer compensation

A system that sometimes stops is annoying. A system that sometimes lies is unusable, because you can never trust any answer it gives. That is why the guiding rule of protocol design is:

Safety unconditionally; liveness when the system model's assumptions hold.

Concretely: anything that depends on timing (timeouts, leases, clock readings) should only be allowed to affect liveness. If a timing assumption can affect safety, you need a defence for when it is violated — such as fencing tokens, or Spanner-style explicit uncertainty bounds with commit-wait.

"Eventually" can be useless

Liveness properties promise nothing about when. A system whose replicas converge "eventually" but only after three days satisfies the property. Production systems therefore pair liveness properties with measured bounds — replication lag percentiles, election durations, time-to-convergence — even though the proofs do not mention them.

6.4 Checking safety and liveness in practice

Because safety violations are finite counterexamples, they are what testing tools look for. Jepsen-style tests record a history of operations, then run a checker that searches for a finite violation (a lost acknowledged write, a stale read that breaks linearizability). Model checkers like TLA+'s TLC exhaustively explore states looking for an invariant violation — a safety check. Liveness requires reasoning about infinite behaviours (TLA+ supports this with temporal properties and fairness assumptions), which is harder and slower, so in practice teams check safety exhaustively and liveness on small models.

A tiny safety checker over a recorded trace — "at most one leader per term" — shows how mechanical this is:

from collections import defaultdict

def check_single_leader_per_term(events):
    """events: iterable of dicts like {"t": 12.5, "node": "n2", "type": "became_leader", "term": 7}.
    Returns the first violation (a finite counterexample) or None."""
    leaders = defaultdict(set)
    for e in sorted(events, key=lambda e: e["t"]):
        if e["type"] == "became_leader":
            leaders[e["term"]].add(e["node"])
            if len(leaders[e["term"]]) > 1:
                return {"term": e["term"], "leaders": sorted(leaders[e["term"]]), "at": e["t"]}
    return None

if __name__ == "__main__":
    ok = [{"t": 1, "node": "a", "type": "became_leader", "term": 1},
          {"t": 5, "node": "b", "type": "became_leader", "term": 2}]
    bad = ok + [{"t": 6, "node": "c", "type": "became_leader", "term": 2}]
    assert check_single_leader_per_term(ok) is None
    assert check_single_leader_per_term(bad) == {"term": 2, "leaders": ["b", "c"], "at": 6}
    print("ok")

There is no equivalent finite checker for "a leader is eventually elected" — you can only say "not yet, within the window I watched."


7. Measures of Correctness

Safety and liveness are the shape of correctness. The content — what exactly counts as "bad" — comes from correctness conditions such as linearizability and serializability. It helps to see these as safety properties over histories.

7.1 Histories

A history is the record of operations that clients invoked and the responses they received, with their real-time intervals:

Client 1: |--- write(x, 1) ---|
Client 2:          |--- read(x) → 0 ---|
Client 3:                                   |--- read(x) → 1 ---|

A correctness condition is a rule that says which histories are allowed. A system satisfies the condition if every history it can produce is allowed.

7.2 The main conditions as properties

ConditionApplies toAllowed histories (informal)Safety or liveness?
LinearizabilitySingle objects (registers, queues)Every operation appears to take effect atomically at some instant between its invocation and responseSafety
Sequential consistencySingle or multiple objectsSome total order of operations consistent with each client's program orderSafety
Causal consistencyMultiple objectsEvery client sees causally related writes in causal orderSafety
SerializabilityTransactions over many objectsEquivalent to some serial execution of the committed transactionsSafety
Strict serializabilityTransactionsSerializable, and the serial order respects real timeSafety
Eventual consistencyReplicated objectsIf writes stop, replicas eventually agreeLiveness
Wait-freedom / availabilityAny operationEvery request to a non-failed node eventually completesLiveness

Two distinctions trip up even experienced engineers:

  • Linearizability vs serializability. Linearizability is about single operations on single objects and respects real time. Serializability is about transactions over many objects and says nothing about real time — a serializable database may order your transaction before one that committed an hour earlier. Strict serializability is both. The Consistency Models page covers the full hierarchy, and Isolation Levels covers the transactional side.
  • Consistency in CAP vs C in ACID. CAP's "C" is linearizability. ACID's "C" is "transactions preserve application invariants" — a property of your application code, not of the database.

7.3 Correctness depends on the model, too

A correctness condition is only meaningful together with the system model. "Linearizable" for a system that assumes crash-stop failures says nothing about what happens when a node recovers with a stale disk. "Serializable" for a system that assumes bounded clock skew (as some timestamp-ordered databases do) may not hold if skew exceeds the bound. When a vendor claims a guarantee, the follow-up question is always: under which failures?


8. Stateless vs Stateful Services

Most of the difficulty in distributed systems is the difficulty of state. It is worth being precise about why.

8.1 Stateless services

A stateless service keeps no data that must outlive a single request. Any instance can serve any request, and instances are interchangeable.

  • Failure handling: if an instance dies, retry on another one. No data is lost because there was none.
  • Scaling: add instances behind a load balancer.
  • System model: you barely need one. Crash-stop is fine, timing failures are just latency, and partitions only matter for reaching the backends.

Of course, "stateless" services push their state somewhere: a database, a cache, an object store. The statelessness is real for the service and an illusion for the system — the hard problems have moved, not vanished.

8.2 Stateful services

A stateful service holds data that must survive across requests and failures: databases, queues, lock services, caches that are a source of truth, session stores.

What state makes hard:

ProblemWhy it only exists with state
DurabilityData must survive crashes → crash-recovery model, fsync, WAL
ReplicationOne copy is a single point of failure, so you need copies → they can diverge
ConsistencyCopies diverge → you must define which divergences are acceptable
FailoverA replica takes over → it must have everything the old primary acknowledged
IdentityInstances are no longer interchangeable; node 3 holds shard 17
RebalancingMoving state takes time and bandwidth; you cannot just start a new instance
RecoveryA restarted node must catch up on what it missed before serving
UpgradesOn-disk formats and wire protocols must be compatible across versions during a rolling upgrade

The general strategy is to concentrate state into a small number of well-designed components — a replicated log, a consensus group, a database — and keep everything else stateless. The rest of this section is mostly about how those components are built: Replication, Quorums & Leaderless Replication, and Replicated State Machines.

8.3 Soft state: a useful middle ground

Some state can be reconstructed if lost: a cache backed by a database, a routing table rebuilt from gossip, a materialised view rebuilt from a log. Treating such state as "soft" lets you use a cheaper system model (crash-stop, lose it all, rebuild) for that component. The danger is when soft state silently becomes hard state — a cache that has become the only copy of some data, or a "temporary" queue whose contents are not anywhere else.


9. How Real Systems Pick a Model

Production systems almost never pick a single textbook model. They mix assumptions per concern. Here is what some well-known systems assume — to the best of what their documentation and papers state.

SystemTimingProcess failuresNetworkWhere timing creeps in
etcd (Raft)Partially synchronousCrash-recovery, durable WALPartitions tolerated, majority side progressesElection timeouts (progress only), optional lease-based reads
ZooKeeper (Zab)Partially synchronousCrash-recoveryMajority side progressesSession timeouts for ephemeral nodes
CassandraAsynchronous replication, timeouts for request handlingCrash-recoveryDesigned to stay available under partitionsLast-write-wins uses client/coordinator timestamps → clock skew affects which write wins
Riak (KV)AsynchronousCrash-recoveryAvailable under partitions (sloppy quorums)Mostly avoided — causality tracked with version vectors
SpannerPartially synchronous for Paxos, bounded clock uncertainty for external consistencyCrash-recoveryMajority per Paxos groupTrueTime: if real clock error exceeds the reported bound, external consistency can break
CockroachDBPartially synchronous Raft, maximum clock offset for transaction orderingCrash-recoveryMajority per rangeNodes are designed to shut themselves down when they detect that their clock offset from peers is approaching the configured maximum (default 500 ms)
PBFT-style chainsPartially synchronousByzantine (f of 3f+1)Partitions toleratedView-change timeouts (progress only)

Patterns worth noticing:

  1. Crash-recovery + partial synchrony is the default for strongly consistent infrastructure. It matches reality reasonably well and admits efficient protocols.
  2. Byzantine models are rare inside a single organisation, because the 3f+1 cost and cryptographic overhead are high and the threat is usually addressed with authentication, checksums and isolation instead. Checksums turn many arbitrary corruptions into detectable omissions — "drop the message" — moving them back into a cheaper model.
  3. Bounded clocks are used deliberately, with a safety valve. Spanner and CockroachDB both make explicit clock assumptions, and both have mechanisms (commit-wait over a measured uncertainty interval, self-termination on excessive offset) for when the assumption is threatened.
  4. AP systems trade a timing assumption for a semantic one. Cassandra's last-write-wins avoids coordination but makes wall-clock skew decide conflicts — a silent safety trade most users never consciously made.

9.1 What breaks when reality violates the model

The most valuable question to ask of any design is: "what happens when assumption X is false?" Here is how common violations play out.

Violated assumptionWhat actually happenedConsequence if unprotectedStandard defence
"Paused processes are dead" (timing)GC pause of 15 s on the lock holderHolder resumes and writes after its lease expired, alongside the new holderFencing tokens checked by the storage layer
"Clocks are within ε"NTP misconfiguration, VM clock jumpLease overlap, LWW picks the wrong write, timestamps go backwardsMonotonic clocks for durations, HLCs, max-offset enforcement
"Disk keeps what was fsync'd" (crash-recovery)Write cache without power-loss protection, or fsync disabledRecovered node forgot votes/promises → two leaders, lost commitsProper fsync, enterprise disks, checksummed logs
"Faulty nodes stop" (crash)Bit flip or bug makes a node send corrupt stateCorruption propagates to all replicasChecksums on messages and on disk, end-to-end verification
"Partitions are symmetric/total"Partial or one-way link failureLeader flapping, both sides think they are primaryPreVote/CheckQuorum, bidirectional health checks
"Membership is static"Operator replaces a node reusing the old identityOld and new incarnations both participateUnique incarnation IDs, joint consensus for membership changes

War Story — GitHub, October 2018

GitHub published a detailed post-incident analysis of an outage on 21 October 2018. Routine network maintenance caused connectivity between their US East Coast network hub and primary US East Coast data center to be lost for 43 seconds. During that window their MySQL topology manager (Orchestrator, which uses Raft among its own nodes) promoted primaries in a West Coast data center. When connectivity returned, the East Coast primaries had accepted writes that had not been replicated West, and the West Coast primaries had accepted new writes too. Because the two sets of writes could not simply be merged, GitHub chose to restore from backups and replay, and the site ran degraded for just over 24 hours. In model terms: a short partition — well within "partially synchronous" behaviour — combined with an automated failover whose safety depended on the old primary having replicated everything before it became unreachable. The lesson the post draws is about failover policy across regions, but the general lesson is ours: the failover rule was making an irreversible decision based on a timeout.

War Story — Cloudflare, November 2020

Cloudflare wrote up an incident titled "A Byzantine failure in the real world". A network switch began misbehaving in a way that let some nodes see each other while others could not — a partial, inconsistent view of connectivity rather than a clean partition. Their etcd cluster, which coordinated failover for a database cluster, lost and re-elected leaders repeatedly, and the systems depending on it (including database failover tooling) took disruptive actions. Raft was operating within its model — it stayed safe — but the liveness loss in the coordination layer, plus automation built on top of it, caused a significant outage. The post is a good read precisely because the failure was not "a node crashed" but "the network lied in different ways to different nodes" — something the crash-fault model does not describe directly.

War Story (illustrative) — the replica that came back from the past

A team ran a three-node consensus-based configuration store on cloud VMs. To speed up a maintenance window, an engineer restored one node from a week-old disk snapshot and restarted it with its original node ID. The node rejoined with a log that ended a week ago, an old currentTerm, and — critically — no memory of the votes it had cast since. During a later leader election it voted for a candidate whose log was missing recent entries, which a correctly-remembering node would have refused. The store was briefly led by a node that did not have every committed entry. Nothing in the code was wrong: the operator had violated the crash-recovery model's core assumption, that stable storage is never rolled back. The fix was procedural — a restored node must rejoin as a brand-new member via a membership change, never under its old identity.

9.2 Choosing a model for your own design

A practical checklist when designing a stateful component:

  1. Write down the process model. Do nodes restart with their disks? Can disks be rolled back (snapshots, restores)? Is memory corruption in scope?
  2. Write down the timing model. Which decisions depend on timeouts or clocks? For each, ask: if this timeout fires on a healthy node, is the result slower or wrong?
  3. Write down the network model. What happens in a partial partition? An asymmetric one? A 30-second one in the middle of a failover?
  4. Classify each guarantee as safety or liveness. Make sure every safety property holds under the weakest timing model you can afford.
  5. Look for irreversible actions taken on suspicion. Failovers, lease grants, deletions and promotions triggered by timeouts are where real outages hide.
  6. Decide how you will detect violations. Clock-offset monitoring, checksums, invariant checks in production, Jepsen-style tests in CI.
flowchart TD
    Q1{"Does a timeout or clock<br/>reading drive this decision?"} -->|"No"| OK["Safe under asynchrony"]
    Q1 -->|"Yes"| Q2{"If it fires on a healthy<br/>node, is the result just slower?"}
    Q2 -->|"Yes"| LIVE["Liveness only — fine,<br/>tune with backoff"]
    Q2 -->|"No, it can be wrong"| Q3{"Is there a fencing<br/>or uncertainty defence?"}
    Q3 -->|"Yes"| GUARD["Acceptable — document<br/>and monitor the assumption"]
    Q3 -->|"No"| FIX["Redesign: move the decision<br/>into consensus or add fencing"]

10. Putting It Together

A system model is a contract between an algorithm and its environment. The algorithm promises its properties; the environment promises to stay within the model. When things go wrong in production, it is usually the environment that broke the contract — a pause longer than any timeout, a disk that forgot, a switch that lied — and the algorithm that did exactly what it was proven to do, which was nothing useful outside its model.

The consequences for practice:

  • Prefer algorithms whose safety needs the weakest model (asynchronous, crash-recovery), and let timing only affect liveness.
  • Every place timing affects safety needs an explicit defence and monitoring of the assumption.
  • Durability rules are part of the algorithm. "What must be on disk before replying" is as important as the message flow.
  • Partial failures are the norm, not full crashes and clean partitions.
  • State is where the difficulty lives — keep it in few, well-understood components.

Where to go next:


Interview Questions

1. What is a system model, and why does it matter when someone says an algorithm is "correct"?

A system model specifies timing assumptions (synchronous, partially synchronous, asynchronous), process failure assumptions (crash-stop, crash-recovery, Byzantine…) and network assumptions (fair-loss links, reliable links, partitions). Correctness proofs are conditional on the model: the algorithm guarantees its properties only while the environment stays within the model. "Correct" without a model is meaningless — Paxos is correct for crash faults but not Byzantine ones; a lease-based lock is correct only if clock drift is bounded.

2. Explain partial synchrony and why consensus protocols like Raft are designed for it.

Partial synchrony says the system may behave asynchronously for an unknown period but eventually (after GST) message delays are bounded by some Δ. Raft keeps safety at all times without relying on timing, and uses timeouts only to trigger elections — if a timeout is wrong, the cost is a wasted election, not inconsistency. Once the network stabilises, randomised timeouts let a leader be elected and progress resumes. This sidesteps FLP, which only rules out guaranteed termination in the fully asynchronous model.

3. What is the difference between crash-stop and crash-recovery, and what changes in the protocol?

In crash-stop, a failed node never returns. In crash-recovery, it returns with whatever was on stable storage. Protocols in crash-recovery must persist promises before acting on them — Raft persists currentTerm, votedFor and log entries before replying; Paxos acceptors persist their promised and accepted ballots. Otherwise a recovered node can contradict itself (vote twice in a term), breaking safety. Disk rollbacks (restoring from snapshot under the same identity) violate the model.

4. Why do crash-tolerant consensus protocols need 2f+1 nodes and Byzantine ones 3f+1?

To make progress with f nodes down, quorums can be at most n − f. For crash faults, two quorums of f+1 out of 2f+1 overlap in at least one node, which is honest and carries information between them. For Byzantine faults, quorums of 2f+1 out of 3f+1 overlap in at least f+1 nodes, so at least one honest node is in every overlap even if f liars are present.

5. State the Two Generals problem and give an engineering example.

Two parties must agree to act together over a channel that can lose messages. No finite protocol can guarantee agreement: the sender of the last message never knows if it arrived, and removing it inductively leads to a zero-message protocol. Engineering example: an HTTP request to charge a card times out — the client cannot know whether the charge happened. Responses: retries with idempotency keys, durable decision records that can be queried later (as in 2PC), and accepting probabilistic rather than certain knowledge.

6. Define safety and liveness. Classify "every request eventually gets a response" and "every request gets a response within 200 ms".

Safety: nothing bad ever happens — violations occur at a finite point and are irreparable. Liveness: something good eventually happens — no finite prefix can violate it. "Eventually gets a response" is liveness. "Within 200 ms" is safety, because at 200 ms you can observe a finite violation. Every property is the intersection of a safety and a liveness property (Alpern–Schneider).

7. Why do protocols sacrifice liveness rather than safety when the network misbehaves?

Liveness failures (unavailability) are visible and self-healing — progress resumes when conditions improve. Safety failures (split brain, lost commits, conflicting decisions) are often silent and irreversible: there may be no single correct history to restore. FLP forces a choice in asynchronous systems with crashes, and practical protocols keep safety unconditionally and liveness only after stabilisation.

8. Is linearizability a safety or a liveness property? What about eventual consistency?

Linearizability is a safety property: a non-linearizable history has a finite prefix demonstrating the violation (e.g., a read returning a value older than one already returned to another client after the newer write completed). Eventual consistency is a pure liveness property: it allows any reads in finite time and only requires convergence eventually after writes stop — which is why session guarantees or causal consistency are added for useful safety.

9. Give three ways a lease-based leader can break, and how fencing tokens help.

(a) The leader pauses (GC, VM migration) past its lease and resumes acting as leader. (b) The leader's clock runs slow, so it thinks the lease is still valid. (c) A network delay makes a write issued during the lease arrive at storage after it expired. Fencing tokens — monotonically increasing numbers issued with each lease — let the storage layer reject writes carrying an older token than one it has already seen, so a stale leader's writes are refused regardless of timing.

10. What does state make hard in a distributed system, and how do architectures contain it?

State requires durability (crash-recovery model), replication (copies can diverge), consistency definitions, careful failover (the new primary must have all acknowledged data), stable identities, rebalancing and version-compatible upgrades. Architectures contain this by keeping most services stateless and concentrating state in a few components — replicated logs, consensus groups, databases — whose correctness is carefully argued under an explicit model.

11. Describe a partial partition and why it is harder than a full partition.

In a partial partition some pairs of nodes cannot communicate while others can, e.g., A and C cannot reach each other but both reach B. Failure detectors give inconsistent views: A suspects C, C suspects A, B suspects nobody. Leader election can flap as different nodes repeatedly start elections. Raft's PreVote (don't disrupt a working leader unless a majority agrees an election is needed) and CheckQuorum (a leader steps down if it can't reach a majority) mitigate this.

12. Spanner and CockroachDB both depend on clocks. How does each limit the damage if clocks misbehave?

Spanner's TrueTime exposes an explicit uncertainty interval, and transactions wait out that uncertainty (commit-wait) before acknowledging, so external consistency holds as long as the true error stays within the reported bound. CockroachDB assumes a maximum clock offset between nodes, uses uncertainty intervals on reads (restarting reads that may conflict) and has nodes shut down if they detect their offset from peers exceeds the configured maximum. Both make the assumption explicit, enforce it, and confine its impact.