Skip to main content

Knowledge, Truth, and Lies

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 8 — rewritten and condensed for teaching.

Unreliable Networks and Unreliable Clocks both land on the same uncomfortable conclusion: a node in a distributed system cannot know anything for certain. It can only make inferences from the messages it happens to receive — or, just as informatively, doesn't receive. If a remote node stops responding, there is genuinely no way to distinguish "it crashed," "it's slow," and "the network between us is broken" from where you're sitting. This lesson works through the practical consequences of that uncertainty: how a distributed system can still establish a workable notion of "truth," and what changes once you can no longer even assume the nodes around you are being honest.

The Truth Is Defined by the Majority​

Consider a node with a genuinely strange, asymmetric network fault: it receives every message sent to it perfectly fine, but every outgoing message it sends gets silently dropped or delayed. From that node's own point of view, it's working completely normally — happily processing every incoming request. From everyone else's point of view, it's gone completely silent, and after the usual timeout, they declare it dead. The node itself might even notice its own messages aren't being acknowledged and correctly diagnose a network fault — and it still can't do a single thing about how the rest of the cluster perceives it.

A related, even stranger scenario: a node hits a long stop-the-world GC pause — a full minute, say. Every other node, hearing nothing back, eventually gives up and declares it dead, promoting a replacement. Then the GC finishes, and the "dead" node's threads resume running exactly where they left off — completely unaware that an entire minute has passed, let alone that it's been formally declared dead in its absence.

The lesson underneath both stories: a node cannot fully trust its own judgment of the situation. A distributed system can't safely hinge a decision on any single node's private belief, because that one node could be wrong, or lagging, or simply cut off, at any moment. This is exactly why so many distributed algorithms lean on a quorum — a vote among several nodes — instead: a decision only becomes official once some minimum number of nodes agree on it, deliberately reducing how much the system's correctness depends on any one node's individual, possibly-wrong view of reality.

This applies just as much to declaring nodes dead as to anything else. If a quorum of the cluster votes that some node is dead, then as far as the system is concerned, it is dead — full stop, even if that node still feels perfectly alive and is quietly still processing requests in the background. The most common quorum shape is a strict majority — more than half the nodes — precisely because it's structurally impossible for two different majorities to exist and disagree with each other at the same moment; with 3 nodes you can tolerate 1 failure, with 5 you can tolerate 2, and so on.

Check: truth by majority​

Quiz

Why distributed systems rely on quorums for truth

1 / 3

In the asymmetric network fault scenario (outgoing messages dropped, incoming messages received fine), why can't the affected node do anything to prevent being declared dead?

Pick an answer to see if you are right.

The Leader and the Lock​

Plenty of real systems need to guarantee exactly one of something exists at a time: exactly one leader per partition (to avoid split brain), exactly one client holding a lock on a given resource, exactly one user registered under a given username. Implementing this safely in a distributed system needs real care — because even if a node genuinely, sincerely believes "I am the chosen one," that belief alone proves nothing about whether a quorum of the rest of the cluster still agrees. A node might have been the leader a moment ago, then gotten declared dead during a GC pause (exactly the scenario from the previous section) and quietly demoted — while it's still off in its pause, blissfully unaware anything changed.

If a node keeps acting on a belief the rest of the cluster has already invalidated, real damage follows. Picture a storage service that only allows one client at a time to write to a given file, enforced via a lease obtained from a lock service. Client 1 gets the lease and starts writing — then hits a long pause. While it's paused, its lease expires, and client 2 acquires a fresh lease and starts writing to the same file. Client 1 eventually resumes, still believing (wrongly) that its original lease is valid, and writes too — and now both clients' writes are interleaved, corrupting the file. (This isn't a hypothetical: HBase genuinely shipped with exactly this bug at one point.)

Fencing Tokens: Making the Resource Itself Enforce the Rule​

The fix doesn't require preventing the pause (impossible, as the previous lesson established) — it requires making sure a node acting on a stale belief can't cause damage even when it inevitably tries to. The mechanism: every time the lock service grants a lease, it also hands out a fencing token — a number that strictly increases with every new lease granted. Every write to the protected resource must then include the caller's current fencing token — and the resource itself is required to reject any write carrying a token lower than the highest one it's already seen.

Walk through the earlier scenario again with fencing in place: client 1 gets a lease with token 33, then pauses; its lease expires; client 2 gets a new lease with token 34 and writes successfully, tagged with token 34. Client 1 eventually wakes up, still (wrongly) believing it holds a valid lease, and sends its write tagged with its old token, 33. The storage service, having already seen token 34, simply rejects client 1's stale write outright — no corruption, no coordination needed between the two clients at all. (ZooKeeper users get this almost for free: its zxid or cversion are already monotonically increasing by construction, and work perfectly as fencing tokens.)

The crucial detail: this only works if the resource itself actively checks tokens and rejects stale ones — it is not enough for clients to simply trust their own belief about their lock status, which is precisely the failure mode fencing exists to eliminate. And this constraint, once you sit with it, is arguably a genuine feature rather than an inconvenience: it's simply unwise for any service to assume its clients will always behave well, since clients are frequently written and operated by people whose priorities don't perfectly line up with the service's own.

Practice: enforce fencing at the storage layer​

Implement the resource-side check directly: accept a write only if its token is strictly greater than every token accepted so far.

Check: leadership and fencing tokens​

Quiz

The leader-and-lock problem and fencing tokens

1 / 3

In the HBase-style file corruption bug, what actually causes the file to become corrupted?

Pick an answer to see if you are right.

Byzantine Faults: When Nodes Might Actually Lie​

Fencing tokens solve the problem of a node acting on an honestly outdated belief — but everything in this series so far has quietly assumed nodes are unreliable but honest: they might be slow, or crash, or hold stale state, but if a node responds at all, it's assumed to be playing by the protocol's actual rules, to the best of its own knowledge. Drop that assumption, and everything gets dramatically harder: a Byzantine fault is a node that might send arbitrary, corrupted, or outright deceptive messages — claiming to have received something it never did, for instance — and the problem of reaching agreement in that kind of genuinely untrusting environment is the classic Byzantine Generals Problem: several generals, some secretly traitors, need to agree on a shared battle plan purely by exchanging messengers, with no way to know in advance which of their peers might be actively lying.

A system that keeps working correctly even when some fraction of its nodes are malfunctioning or actively malicious is called Byzantine fault-tolerant. It's a real, necessary property in a couple of specific settings:

  • Aerospace systems, where radiation can flip memory bits and cause a node to behave in genuinely unpredictable, arbitrary ways — and where a system failure (a plane crash, a satellite collision) is catastrophically expensive, so flight control software has to be Byzantine fault-tolerant on principle.
  • Multi-organization systems where participants may not trust each other at all — peer-to-peer networks like blockchain protocols exist specifically to let mutually distrusting parties agree on a shared, tamper-resistant history without needing any central authority to vouch for anyone.

For essentially everything covered elsewhere in this series — ordinary datacenter systems — Byzantine fault tolerance genuinely isn't the right tool. Every node in your own datacenter is presumably under your own organization's control (so, reasonably trusted), and background radiation isn't corrupting your server memory at any meaningful rate. Byzantine-tolerant protocols are also considerably more complex and expensive to run — most require better than two-thirds of participating nodes to be honest and correctly functioning, which is a genuinely demanding bar. It's also worth being explicit about a common point of confusion: running four independent copies of the same buggy software doesn't magically give you Byzantine fault tolerance against that bug — the bug is identical in all four, so it fails identically everywhere it's deployed, tolerant algorithm or not.

That doesn't mean "assume honesty" means "assume infallibility," though — plenty of weaker, cheaper forms of protection against accidental (never malicious) bad data are still absolutely worth building in:

  • Checksums in application-level protocols catch corrupted packets that occasionally slip past TCP/UDP's own built-in checksums.
  • Input sanitization and validation on any publicly-reachable service defends against malformed or malicious user input — SQL injection, XSS, and similarly classic vulnerabilities.
  • Multi-server NTP queries, where a client contacts several time servers at once and simply discards outliers, meaningfully improves robustness against a single misconfigured (not malicious, just wrong) time source — already covered as a concrete example in the previous lesson.

Check: Byzantine faults​

Quiz

Byzantine faults and when they matter

1 / 3

What is the key difference between the "unreliable but honest" node assumption used throughout most of this series, and a Byzantine fault?

Pick an answer to see if you are right.

System Models: Formalizing What You're Actually Assuming​

Every algorithm discussed anywhere in this series needs to tolerate the faults this chapter has walked through — but stating "it should handle faults" isn't precise enough to actually design or prove an algorithm against. A system model makes that precise: an explicit statement of exactly which assumptions an algorithm is allowed to rely on.

Timing models — how much can you assume about delay?

ModelAssumption
SynchronousNetwork delay, process pauses, and clock error all have some fixed, known upper bound — never exceeded
Partially synchronousBehaves synchronously most of the time, but occasionally — unpredictably — exceeds those bounds
AsynchronousNo timing assumptions permitted at all — not even a clock, so timeouts themselves are off the table

Node failure models — how can a node actually fail?

ModelAssumption
Crash-stopA node can fail exactly one way: it crashes, and once it does, it is gone forever
Crash-recoveryA node may crash at any time and may come back later; anything in stable (non-volatile) storage survives the crash, but in-memory state is assumed lost
ByzantineA node may do literally anything — including actively lying, exactly as covered above

For modeling real systems, partial synchrony paired with crash-recovery is, in practice, the most broadly useful combination — genuinely matching how real production hardware and networks actually tend to behave.

Correctness, Safety, and Liveness​

Given a model, an algorithm's correctness can be pinned down as a set of concrete properties it must satisfy — the same way "sorted" for a list just means "for any two adjacent elements, the left one is ≤ the right one." For a fencing-token generator specifically, reasonable properties look like:

  • Uniqueness — no two requests ever receive the same token.
  • Monotonic sequence — if request x fully completed strictly before request y even began, x's token must be smaller than y's.
  • Availability — a node that requests a token, and doesn't itself crash, eventually gets a response.

Notice these three don't all behave the same way — and that distinction has a name. Uniqueness and monotonic sequence are safety properties; availability is a liveness property. Informally, safety is "nothing bad ever happens," liveness is "something good eventually does" — but the precise, technical distinction matters more:

  • Safety violations are permanent and point-in-time. If uniqueness is ever violated, you can identify the exact moment it happened — and once violated, the damage is done; it can never be un-violated after the fact.
  • Liveness properties can be temporarily unsatisfied while still eventually holding. A pending request that hasn't gotten a response yet doesn't mean liveness has failed — there's still genuine hope it resolves correctly, later.

This split turns out to be genuinely useful for reasoning about tricky system models: distributed algorithms typically demand that safety properties hold unconditionally, in every possible situation the model allows — even total network meltdown, even if every single node crashes at once, the algorithm still may never return an outright wrong result. Liveness properties, in sharp contrast, are allowed real caveats — "a request eventually gets a response, provided a majority of nodes haven't crashed, and the network eventually recovers" is a perfectly reasonable, common liveness guarantee. (The partially synchronous model's own definition — "eventually returns to synchronous behavior" — is itself exactly this kind of liveness-style caveat, applied to timing.)

Mapping the Model Back to Reality​

System models are a genuinely powerful tool for reasoning rigorously about an algorithm — but they're still a simplification, and real implementations eventually collide with the parts reality doesn't respect. The crash-recovery model, for instance, assumes stable storage reliably survives a crash — but what if the disk itself is corrupted, or a firmware bug causes a rebooted server to simply fail to recognize its own drives? Quorum-based algorithms specifically depend on a node genuinely, faithfully remembering what it previously claimed to have durably stored — if a node can somehow "forget" data it swore it had (breaking the crash-recovery model's own core assumption), the quorum guarantee the whole algorithm rests on can quietly break along with it.

A theoretical algorithm's description is free to simply declare "this cannot happen" — and reasoning about non-Byzantine systems genuinely does require drawing that kind of line somewhere. But a real implementation still needs actual code for the case where something declared impossible happens anyway — even if that code amounts to nothing more than logging an error and paging a human to clean up the mess by hand. (This gap — between "provably correct on paper" and "handles every real-world edge case in practice" — is arguably a decent working definition of the difference between computer science and software engineering.)

None of this makes the theoretical models worthless — quite the opposite. They're what let you distill an overwhelming, messy reality down into a manageable, precisely statable set of assumptions you can actually reason about and prove things against. Proving an algorithm correct within a stated model doesn't guarantee flawless real-world behavior — but it's an excellent, genuinely necessary first step, because that kind of theoretical analysis reliably surfaces subtle problems that might otherwise stay hidden in a real system for a very long time, right up until some unusual, real-world circumstance finally defeats an assumption nobody had thought to question. Theoretical analysis and empirical testing aren't competitors — they're equally essential, complementary halves of actually getting this right.

Check: system models and correctness​

Quiz

System models, safety, and liveness

1 / 3

Why is the "partially synchronous" timing model generally considered the most realistic for modeling real-world distributed systems, compared to the fully synchronous model?

Pick an answer to see if you are right.

Key takeaways
  • No single node can fully trust its own view of a distributed system's state — which is exactly why quorums (majority votes among nodes) underpin most important decisions, including declaring another node dead.
  • Fencing tokens — strictly increasing numbers issued alongside every lock/lease, checked and enforced by the protected resource itself — are what makes lease-based leadership safe against a node acting on a stale, honestly-outdated belief.
  • Byzantine faults (nodes that may actively lie) require a fundamentally different, more expensive class of algorithm — genuinely necessary in aerospace and trustless multi-organization settings, but rarely justified for an ordinary, single-organization datacenter.
  • A system model makes an algorithm's assumptions explicit and precise — timing models (synchronous / partially synchronous / asynchronous) and failure models (crash-stop / crash-recovery / Byzantine) — with partial synchrony plus crash-recovery being the most broadly realistic combination.
  • Safety properties ("nothing bad ever happens") must hold unconditionally in every situation a model allows; liveness properties ("something good eventually happens") are allowed real, explicit caveats — and proving an algorithm correct within a stated model, while never a substitute for real-world testing, reliably surfaces problems that might otherwise stay hidden until reality finally defeats an unstated assumption.

Further Reading​