How Distributed Systems Decide What Is True

A distributed node sees other nodes through messages. If a reply never arrives, it cannot tell whether the other node failed, the network dropped a packet, or a process paused. The practical question I took from this part of the book is: how can a system make one safe decision when its participants have incomplete, conflicting views?

A majority can revoke a node's authority

Imagine a node that receives requests but cannot send responses. It feels healthy; its peers time out and declare it dead. A one-minute garbage collection pause can produce the same disagreement. The node resumes unaware that the cluster replaced it.

Many distributed algorithms require a quorum for decisions rather than trusting one node's account. The usual quorum is more than half the nodes: two of three, or three of five. This lets the system continue after one or two failures respectively. Two majority quorums overlap, which helps a protocol avoid conflicting decisions when the shared voters follow its rules. A node declared dead by the quorum must step down, even if it knows it is still running. The decision defines operational authority; it does not prove what physically happened to the node.

Why an expired lease can corrupt data

Some work needs exactly one owner: a leader for a database partition, a client holding a lock, or the successful claimant of a username. The problem is that an old owner can continue acting after everyone else has selected a replacement.

💡 Here, a database partition is a shard containing part of the data. A network partition is a communication failure. The latter can cause two nodes to believe they lead the same shard, but the terms describe different things.

Consider a storage file protected by a lease. Client A gets the lease and pauses. Its lease expires; client B gets a new one and successfully writes. A resumes, still believes its old lease is valid, and sends another write. Storage accepts it, corrupting the file. The writes need not happen at the same instant. The mistake is accepting authority that has already expired. The book notes that HBase once had this class of bug.

sequenceDiagram
    participant A as Client A
    participant L as Lock service
    participant B as Client B
    participant S as Storage
    A->>L: Acquire lease
    L-->>A: Lease granted
    Note over A: Process pauses
    Note over L: A lease expires
    B->>L: Acquire lease
    L-->>B: New lease granted
    B->>S: Write file
    S-->>B: Accepted
    Note over A: Process resumes
    A->>S: Write with stale authority
    S-->>A: Incorrectly accepted

Fencing makes the resource reject former owners

A lock service can issue a strictly increasing fencing token with each new lease. Every protected write carries that token. Storage remembers the highest token it has accepted and rejects a lower one.

A receives token 33 and pauses. B receives 34, then storage accepts B's write. When A later writes with 33, storage rejects it. A does not need to notice that its lease expired; the resource enforces the new ownership.

sequenceDiagram
    participant A as Client A
    participant L as Lock service
    participant B as Client B
    participant S as Storage
    L-->>A: Grant token 33
    Note over A: Process pauses
    Note over L: Lease 33 expires
    L-->>B: Grant token 34
    B->>S: Write with 34
    S-->>B: Accept and remember 34
    Note over A: Process resumes
    A->>S: Write with 33
    S-->>A: Reject stale token

The protected resource must perform this check. A client-side lease check still has a race: the client can pause immediately after checking. ZooKeeper's zxid or a znode's cversion can provide increasing values. If a file service cannot compare tokens directly, an operation may sometimes encode the token in its filename, but some enforceable stale-write check is still needed.

The same owner may make several legitimate writes using token 34. Equality alone is not stale. A request ID or payload ID handles duplicate retries; fencing handles an older owner. Also, token 34 alone does not prove its lease remains active right now. A resource can reject it as stale after it has seen a newer token.

💡 Applying this to our clinic workers: A TTL lets another worker take over if one dies. A unique owner value prevents the old worker from releasing or renewing the replacement's lock. Renewal supports long jobs but cannot eliminate pauses. A new generation token, checked in the same database transaction as each clinic write, rejects stale work. Stable payload IDs make retries idempotent. These are application design layers built from the book's lease and fencing principles.

What changes when nodes can lie?

So far, the old client is mistaken but follows the protocol. A malicious client could simply invent token 99. That is a different fault model. The book usually assumes nodes are unreliable but honest: they may be silent, slow, or stale, yet a response follows the protocol to the node's best knowledge. A Byzantine fault allows arbitrary false claims or contradictory messages.

The boxed Byzantine Generals story extends a two-party agreement problem with delayed or lost messengers: now an unknown subset of many participants may be traitors. The name uses the figurative sense of "Byzantine," not a historical claim about those generals. A Byzantine-tolerant protocol must keep its guarantees despite dishonest participants. Most such protocols require more than two-thirds of nodes to behave correctly. For instance, with four replicas and at most one liar, a protocol might require three authenticated, rule-following votes. Two groups of three overlap in at least two replicas, so at least one shared voter is honest. The protocol must still ensure that honest voter cannot approve conflicting final decisions. Progress still depends on the protocol's timing and availability assumptions.

This matters in safety-critical systems vulnerable to hardware corruption and systems shared by organizations that may cheat. Blockchains are an example of agreement without one central authority. In an ordinary datacenter controlled by one organization, Byzantine protocols are usually too complex and costly. They cannot cure a bug shared by identical software on every node. Defending against implementation bugs this way would require independent versions of the software. Nor do these protocols replace authentication, access control, encryption, and firewalls. Public web clients are untrusted, but servers normally validate and sanitize input and escape output instead of running Byzantine consensus with browsers.

Cheaper defenses still help against accidental bad data: application-level checksums for corruption missed by transport checks, range and size checks before a huge allocation, and multiple NTP servers whose error estimates let the client find a majority-agreed time range and reject an outlier. These checks do not resist a determined adversary.

A system model states what the algorithm may assume

To evaluate a guarantee, we first name the failures it must survive. A synchronous model gives known upper bounds for message delays, process pauses, and clock errors. It does not require zero delay or equal clocks. A partially synchronous model allows those bounds to fail for a while, perhaps by an arbitrary amount, but assumes bounded behavior eventually returns. An asynchronous model allows no timing assumption or clock, so an algorithm cannot rely on timeouts.

💡 These timing models describe the environment, not whether worker code uses async/await. When clinic worker B hears nothing from A, a timeout may be a false suspicion under partial synchrony. A can later resume after B takes over.

The node model is a separate dimension. Crash-stop nodes never return. Crash-recovery nodes can restart after losing memory while their durable storage is assumed to survive. Byzantine nodes may do anything. Partial synchrony plus crash-recovery is often the useful model for production systems, but its storage assumption must be checked against reality.

Correctness has two kinds of promise

A sorting algorithm needs a precise rule for ordered output. A fencing-token service similarly needs stated properties: no duplicate token; a later request receives a greater token if the earlier request finished before it began; and a requester that does not crash eventually receives an answer under suitable recovery conditions.

The first two are safety properties. If the service issues a duplicate or reverses the required order, we can identify the event where it went wrong; a later correction cannot erase that violation. The third is liveness: progress can be absent now and arrive later. Eventual consistency has the same future-oriented shape.

During a total outage, a safe service may stop answering rather than invent a conflicting token. It can promise progress only under conditions such as a surviving majority and eventual network recovery. "Eventually" sets no fixed deadline. Under partial synchrony, the bad period must end for the liveness argument to work.

For our clinic example, safety means an older worker cannot commit a clinic write once the database has atomically recorded a newer generation. Liveness means another worker can eventually continue when enough infrastructure survives and communication recovers.

Proofs still meet messy production failures

A crash-recovery proof may assume stable storage remembers a node's data. Real disks can corrupt or lose it; misconfiguration can erase it; firmware can fail to recognize a drive. A node that forgets data it previously claimed to store can break a quorum argument. An implementation needs a response even to a supposedly impossible event, sometimes stopping and asking an operator to repair the state. A proof shows correctness under its model; testing checks how closely the implementation and hardware match that model.

My final takeaway is to treat silence as incomplete evidence and authority as something the resource must enforce. Partial failures define distributed systems: some nodes keep running while others fail or stall. Even a node that only slows drastically can be harder to handle than a dead one. Clocks can drift or jump, and a node usually does not know its clock's error bound. If one machine satisfies the need, it avoids this complexity. Distribution can still provide fault tolerance and lower latency near users. Hard deadlines and bounded networks are possible but costly in capacity and utilization. Supercomputers may restart after one component fails; distributed services aim to handle node failures without stopping the service, although a bad configuration sent to every node can still bring it down.

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.