Distributed Systems · 1 of 4

The Trouble with Distributed Systems

On one machine, things work or they crash. Across a network, a silent peer might be dead, slow, paused or cut off, and you can't tell which. Clocks drift, processes freeze, and the only truth you get is the messages that arrive.

≈ 30 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

Partial failure

A program on one computer is, almost always, deterministic. It either works or it fails outright: a bad memory module gives you a kernel panic, not a slightly wrong sum. Hardware is built to behave that way on purpose. When something is wrong inside the box, it’s better to crash than to lie.

Put several computers on a network and that property is gone. Some parts of the system can be broken while others work fine, and the broken parts can be broken in ways nobody predicted. That is a partial failure, and it’s nondeterministic: the same operation might succeed, fail, or do something in between, and you may not even find out which.

A process in a distributed system knows only two things: its own local state, and the messages that reach it. Everything else (whether a peer is up, whether a write landed, what time it is) is an inference from those messages. The rest of this lesson is about how those inferences go wrong:

  • the network loses, delays, reorders and duplicates messages;
  • clocks disagree with each other and jump;
  • processes stop for seconds at a time without noticing.

Unreliable networks

The networks inside data centres, and between them, are asynchronous packet networks. A node can send a packet, but the network promises nothing about whether or when it arrives. When you send a request and wait, the hero diagram above is the whole story: the request might be lost, the remote node might be dead or paused, or the reply might be lost. The sender can’t tell those apart. It can’t even tell whether the work happened.

Networks also delay messages, sometimes enormously. Every hop is a queue:

  • a switch queues packets when several senders target one port, and drops them when the queue fills;
  • the receiving OS queues them when every CPU core is busy;
  • a hypervisor queues them while it runs another virtual machine;
  • TCP hides a lost packet by retransmitting it, but only after a timeout (at least 200 ms on Linux), so a dropped packet shows up as latency, not as an error.

Delays are rarely small and well-behaved. In December 2012 a switch fault at GitHub blocked traffic between its access switches for 90 seconds. File-server pairs declared each other dead and sent each other “shoot the other node” messages, the network held those messages up, and when it recovered both halves of some pairs shot each other.

5.2 / daynetwork device failures, on average, across Microsoft data centres (2011)
40.8 / daynetwork link failures in the same study
40%how much redundant network paths cut the median impact of a failure. Not 100%.

That study, of several Microsoft data centres over a year, found load balancers among the least reliable devices and redundancy far less effective than the topology diagrams suggest. A redundant pair of switches still shares software, configuration and the person who upgrades them both on the same night.

The Fallacies of Distributed Computing, collected at Sun in the 1990s, start with “the network is reliable” and “latency is zero”. Thirty years on, they’re still the most common hidden assumptions in code review.

Network partitions

When part of the network is cut off from the rest, that’s a network partition: the nodes are all running, but some can’t talk to others. To each side, the other side looks exactly like a set of crashed machines.

One network, two sides

Side ASide B
Nobody crashed. Each side just stopped receiving messages from the other.

The only safe rule is to let at most one side act. Majority-based systems do this naturally: a side with a majority of nodes can elect a leader and commit writes, and a minority side can’t. A system that lets both sides keep accepting writes ends up with two leaders, a Split Brain, and two histories that can’t be merged.

Partitions aren’t exotic. A 2018 study of 136 partition-related failures across 25 widely used systems (MongoDB, Elasticsearch, Redis, ZooKeeper, Kafka, Cassandra, HBase and others) found:

80%of the failures were catastrophic: data loss, stale reads, broken locks
88%could be triggered by isolating a single node
29%were caused by partial partitions

Data loss was the most common outcome, leader election the most fragile mechanism, and 21% of the failures left damage that persisted after the network healed. Most could be reproduced with three nodes.

That 29% is the nasty kind. In a partial partition, some nodes can talk to each other and some can’t, so the nodes disagree about who is up. Cloudflare met one on November 2, 2020:

A partial partition

Each node’s view is locally reasonable. Together they can’t make progress.

The switch recovered on its own after six minutes. But etcd’s outage had already set off automation that promoted a database replica; a separate bug meant every other replica then had to be rebuilt, and the overloaded authentication database kept Cloudflare’s API and dashboard impaired for 6 hours 33 minutes. Raft’s Pre-Vote phase (an etcd option since 3.4, on by default since 3.5), paired with CheckQuorum, targets exactly this pattern: a node must learn that it could win before it bumps the term, and a peer that still hears a healthy leader turns it down.

Detecting failure

Since you can’t observe a crash directly, you infer one from silence: no reply within a timeout. Choosing the timeout is a trade with no free side.

  • Too short, and a node that’s merely slow gets declared dead. Its work is handed to someone else, which adds load, which makes more nodes slow, which can cascade. If the node was in the middle of an action, the action may now happen twice.
  • Too long, and a node that really is dead keeps receiving requests that hang until the timeout expires.

If the network guaranteed a maximum delay d and nodes answered within r, a timeout of 2d + r would be exact. Real networks guarantee neither, so a timeout is always a guess about a distribution.

A timeout is a cut through a distribution

Fixed timeouts are tuned for one network. Accrual detectors re-tune themselves continuously.

The phi accrual failure detector (Hayashibara et al., 2004) replaces the yes/no timeout with a suspicion level. It keeps a sliding window of heartbeat gaps, estimates their distribution, and outputs φ = −log₁₀ of the probability that a heartbeat would still arrive after this much silence. Callers pick a threshold. Cassandra and Akka use it; Cassandra’s default phi_convict_threshold is 8, and its implementation models gaps as exponential, so φ = 8 means roughly 18 average heartbeat intervals of silence. Its docs suggest raising it to 10–12 on Amazon EC2, where network congestion is common.

Even then, the detector’s answer is “probably dead”, never “dead”. Only the node itself, or a power switch, knows for sure. Some environments give stronger signals (a switch reporting a link down, a process manager reporting an exit), and a good system uses them, but it must still cope with the case where no signal comes at all.

Gossip and SWIM

In a cluster of thousands, everyone heartbeating everyone costs O(n²) messages. Gossip protocols spread information the way rumours spread: each node periodically tells a few random peers what it knows, and they pass it on. News reaches everyone in O(log n) rounds, with a constant load per node.

SWIM (Das, Gupta and Motivala, 2002) combines gossip with a careful failure detector, and it’s what HashiCorp’s memberlist (under Consul, Nomad and Serf) implements.

SWIM failure detection

Indirect probes separate a dead node from a bad network path. Suspicion separates a slow node from a dead one.

Its two ideas are worth stealing anywhere:

  • Indirect probes. Before blaming the target, ask other nodes to check. A single bad path no longer looks like a death.
  • Suspicion before death. A suspected node that’s actually alive hears the rumour about itself and refutes it with a higher incarnation number.

In 2017 HashiCorp published Lifeguard, which adds one more: a node whose own probes keep timing out treats itself as the likely problem (an overloaded CPU, a slow event loop) and slows down its accusations. The paper reports false positives cut by more than 50×; HashiCorp’s new memberlist defaults gave a 20× reduction while detecting real failures 20% faster.

Unreliable clocks

Clocks matter for durations (timeouts, latency percentiles, lease expiry) and for points in time (when a write happened, when a cache entry expires). Every machine has its own clock, and they disagree.

Each machine actually has two:

  • The time-of-day clock (CLOCK_REALTIME in Linux, System.currentTimeMillis() in Java) returns wall time. NTP adjusts it, and when the machine is far off, NTP steps it, possibly backwards. It’s fit for comparing across machines, roughly, and unfit for measuring elapsed time.
  • The monotonic clock (CLOCK_MONOTONIC, System.nanoTime()) only moves forward. Its absolute value is meaningless (often time since boot), but the difference between two readings is a real duration. Use it for every timeout and latency measurement.

The quartz crystal under both drifts with temperature. Google’s time infrastructure assumes a worst case of 200 µs per second, about 17 seconds a day if a machine never resynchronizes. NTP over the public internet usually holds machines within tens of milliseconds; on a good LAN, under a millisecond. Worse happens routinely: a misconfigured NTP server, a firewall blocking it, a VM resumed from suspension with its clock frozen.

The difference between two machines’ clocks is clock skew, and it quietly corrupts any logic that orders events by timestamp. The classic victim is Last Write Wins:

Skew reorders cause and effect

Last write wins keeps the write with the biggest timestamp, which is not the same thing as the last write.

Nothing in that trace looks wrong locally. Every node did exactly what the algorithm says, and the database discarded a write it had acknowledged. The deeper lesson: a clock reading is a range, not a point. If the skew bound is 10 ms, two timestamps less than 10 ms apart have no knowable order.

A few systems make the range explicit. Google’s TrueTime returns an interval with every reading. Amazon’s Time Sync Service, since November 2023, keeps supported EC2 instances within microseconds of UTC using hardware reference clocks, and its open-source ClockBound daemon gives applications the error bound to go with each reading. The Time, Clocks & Ordering lesson builds ordering on top of both.

Leap seconds and monotonic clocks

Leap seconds have been a dependable source of clock bugs in production. A positive leap second inserts 23:59:60, a minute with 61 seconds. In 2012 one hung Linux machines across the internet. At the next-but-one, on December 31, 2016, Cloudflare’s DNS fell over a subtraction in Go:

When time goes backwards

Durations need the monotonic clock. Wall clocks are for telling time.

Only lookups of CNAME records were hit, and Cloudflare patched the worst-affected machines within 90 minutes, but the episode is a perfect specimen: correct-looking code (end - start) whose hidden assumption (wall time only moves forward) was false for one second every few years. Go 1.9 shipped in August 2017 with monotonic readings inside time.Time, so the same code is now correct by default.

Leap seconds themselves are ending. In October 2026 the General Conference on Weights and Measures voted that from 20 May 2027 UTC runs continuously, with no more leap seconds; the last one was that 2016 insertion. That removes one trigger, not the class of bug. NTP still steps clocks, VMs still resume with stale clocks, and operators still fix wrong time by hand.

Process pauses

Here’s a pattern that looks safe. A node holds a lease, a lock that expires, so a crashed holder can’t block everyone forever. Before each write it checks that the lease has time left, then writes.

The flaw is the gap between the check and the write. A thread can be stopped at any instruction, for a long time, with no indication to the code that anything happened:

  • Garbage collection. Stop-the-world collectors have paused JVMs for several minutes. Modern low-pause collectors shrink this enormously, but not to zero, and not for every runtime.
  • Virtualization. A VM can be suspended and live-migrated; a hypervisor can deschedule a vCPU (“steal time”).
  • The OS. Memory pressure swaps pages to disk mid-function. A synchronous disk read on a dying disk can block for seconds. Someone sends SIGSTOP. A laptop lid closes.

A pause outlives a lease

From the paused process’s point of view, no time passed at all.

This isn’t hypothetical: HBase used to have exactly this bug, where a region server could pause long enough for its ZooKeeper session to expire, and keep writing after its regions were reassigned. A node in a distributed system must assume its execution can freeze at any point and that the world moves on while it’s frozen. Checking a clock more carefully doesn’t help, because the pause can fall right after the check.

Fencing tokens

You can’t stop pauses, so stop paused nodes from doing damage. Make the lock service hand out a fencing token, a number that increases with every grant, and make the resource check it.

Fencing tokens

The client can be wrong about time. The storage only needs to compare two integers.

Real systems already produce such numbers. Google’s Chubby calls them sequencers. In ZooKeeper, the zxid or a znode’s version works. Kafka fences zombie controllers, partition leaders and transactional producers with epochs. And since November 2024, Amazon S3 supports conditional writes with If-Match on an object’s ETag, a compare-and-swap that lets object storage reject a writer working from a stale version.

In February 2016 Martin Kleppmann used this argument against Redlock, Redis’s multi-node locking algorithm: it hands out no fencing token, and it depends on bounded pauses, network delays and clock drift for safety. Redis creator Salvatore Sanfilippo replied the next day that Redlock checks elapsed time after acquiring the lock, and that if the resource can do check-and-set with a random token you barely need a lock at all. The thread is worth reading in full. The settled takeaway: a lock used for efficiency (avoid doing work twice) can be loose; a lock used for correctness needs fencing at the resource, plus a lock service built on consensus.

Byzantine faults

Fencing assumes nodes are honest: wrong about time, perhaps, but not lying. A node that sends arbitrary or deliberately false messages commits a Byzantine fault, after Lamport, Shostak and Pease’s 1982 “Byzantine Generals” paper. Tolerating f such nodes takes at least 3f + 1 nodes and expensive protocols.

Inside one company’s data centre you usually don’t pay that price: you control the machines, and an attacker who owns one probably owns them all, since they run the same software. Byzantine tolerance matters where nodes don’t trust each other (blockchains, cross-organization systems) and where radiation flips bits (aircraft, spacecraft).

What you do want are cheap defences against accidental lies: checksums on network payloads and on disk, validation of every input from a client, and multiple NTP servers so one wrong source gets outvoted. Cloudflare titled its 2020 post “A Byzantine failure in the real world” and later added a note that experts classify it as an omission fault: messages went missing, nobody lied. The distinction matters, because omission faults are what ordinary crash-tolerant protocols are supposed to survive.

System models

To prove an algorithm correct you have to say what can go wrong. A system model names it in two parts.

Timing model Assumes Realistic?
Synchronous bounded delay, bounded pauses, bounded drift no
Partially synchronous usually bounded, but occasionally anything yes: the usual target
Asynchronous no timing assumptions, not even timeouts very restrictive
Node model A node may…
Crash-stop stop and never return
Crash-recovery stop and come back, keeping what was on disk
Byzantine do anything at all, including lie

Most practical algorithms (Raft, Paxos, ZooKeeper’s Zab) assume partial synchrony with crash-recovery. Their guarantees split in two. Safety properties (“nothing bad happens”: no two leaders in one term, no lost committed write) must hold always, even when every timing assumption is broken. Liveness properties (“something good eventually happens”: a leader is elected, a request completes) may wait until the network behaves. That’s why a well-built consensus system under partition stops making progress instead of making mistakes.

Trade-offs

Decision One way The other way
Timeout length short: fast failover, false positives, duplicate work long: fewer false alarms, slow detection, hung requests
Failure detector fixed timeout: simple, wrong when the network changes accrual or SWIM: adapts, more machinery to tune
Ordering events wall-clock timestamps: cheap, silently wrong under skew logical clocks or consensus: correct, more coordination
Leases short: fast takeover, more renewals, more sensitive to pauses long: fewer renewals, slow recovery after a real crash
Mutual exclusion lock alone: easy, unsafe across pauses lock + fencing token: safe, the resource must check
Fault model crash-tolerant: cheap, assumes honesty Byzantine-tolerant: 3f + 1 nodes, slow, needed only without trust

In the real world

  • Jepsen. Kyle Kingsbury’s analyses test databases under exactly these faults: partitions, clock skew, paused processes. A long line of them since 2013 found acknowledged writes lost and stale reads served by systems whose docs promised otherwise. Read one before you trust a vendor’s consistency claims.
  • Cassandra gossips every second with a few peers and judges liveness with a phi accrual detector, so a node is judged on its own recent heartbeat history rather than one global number.
  • Consul and Nomad (HashiCorp memberlist) run SWIM with Lifeguard across clusters of thousands of agents.
  • Cloudflare, 2017 and 2020: one clock bug, one partial partition, two well-written postmortems that are worth reading as a pair.
  • AWS smears leap seconds and, since 2023, offers microsecond-accurate time with ClockBound error bounds; Google has smeared for its own fleet and public NTP for years, now with a 24-hour noon-to-noon smear.

Pitfalls

  • Measuring durations with the wall clock. Any now() − start on a time-of-day clock can go negative or jump forward. Use the monotonic clock.
  • “Timed out” means “didn’t happen”. It means unknown. The server may have done the work, so retries need idempotency.
  • Trusting a lease check. A pause can fall between the check and the action. Fence at the resource.
  • Ordering by timestamp across machines. Last write wins with skewed clocks silently drops writes.
  • Testing only clean crashes. The bugs live in partial partitions, one-way links and slow nodes. Inject those.
  • A two-node cluster. No side of a partition can hold a majority. Add a third voter.

Recall

Go deeper

Keep going

The atomic notes for this lesson live in the knowledge graph:

Next on the map: Time, Clocks & Ordering (ordering events without trusting clocks) and Consensus (getting nodes to agree despite everything in this lesson).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Next in Distributed SystemsTime, Clocks & Ordering