The SRE Book, Ten Years On — Part 9: Agreeing to Agree

Distributed systems literature has one warning worth quoting above every other:

Whenever you see leader election, critical shared state, or distributed locking, think distributed consensus — any lesser approach is a ticking time bomb.

That warning earns its bombast with three real case studies, not just the aphorism. This post follows the same order the case studies force on you.

The Same Mistake, Three Disguises

Most systems that need to agree on something — who’s the leader, what’s the current config, did this job run — are built on the same mistake, worn in three disguises: timeouts as leadership (whoever’s heartbeat lapsed must be dead, so I’m in charge), human escalation as a safety valve (when in doubt, page someone), and gossip as group membership (we’ll just talk amongst ourselves and sort it out). All three fail identically, and each one deserves its own postmortem.

Case one: a content-repository service runs pairs of file servers, one leader and one follower per pair, monitoring each other by heartbeat. Lose the heartbeat, and the surviving node issues STONITH — Shoot The Other Node In The Head — and takes over. It’s an industry-standard pattern.

It’s also conceptually unsound: if the network merely gets slow rather than actually failing, both nodes can miss each other’s heartbeats, both fire STONITH, and now you either have two masters writing divergent data or two dead nodes and no service at all. The diagnosis is precise: this is a leader-election problem, and leader election is asynchronous distributed consensus wearing a disguise — heartbeats cannot solve it, because a slow network and a dead peer look identical from one side of the wire.

Case two tries to route around the problem by adding a human: a sharded database promotes a secondary to primary on failure, but if the primary can’t confirm the secondary’s health, it makes itself unavailable and pages an engineer rather than risk split-brain. This doesn’t corrupt data — but it trades availability for safety, and it does so exactly when a human is least equipped to help: during a broader infrastructure incident, when the responding engineer is already buried in other pages. One line lands hardest here: if the network is so damaged that an automated consensus system can’t elect a leader, a human sitting at a keyboard is not better positioned to do so.

Case three replaces heartbeats with gossip: nodes discover each other and elect a leader by talking amongst themselves. A network partition splits the cluster into two islands; each island, unable to see the other, elects its own leader; both islands accept writes and deletes. Group membership is also a consensus problem, and gossip is exactly as unsound a solution to it as heartbeats are to leader election.

The unifying diagnosis, stated as bluntly as SRE literature ever gets: master election, group membership, distributed locking and leasing, reliable queuing, and any critical shared state that multiple processes must view consistently are all the same problem — and every ad-hoc attempt to solve it informally has the same failure mode, because none of them can distinguish “the peer is dead” from “the network is broken.” Only a formally proven, extensively tested consensus algorithm can.

Why the Shortcuts Can’t Work: CAP and FLP

All three case studies ground out in the CAP theorem: a distributed system cannot simultaneously guarantee Consistency (every node sees the same data), Availability (every request gets a response), and Partition tolerance (the system keeps working when the network splits). Because partitions are physically inevitable — cables get cut, switches misconfigure, packets queue and drop — CAP isn’t a theoretical curiosity, it’s a forced choice every distributed system makes, whether its designers realize it or not.

When a partition happens, you either stop answering some requests (sacrifice availability) or you answer with data that might disagree between nodes (sacrifice consistency).

There’s a clear side to take here. A newer generation of datastores offers BASE semantics (Basically Available, Soft state, Eventual consistency) instead of the traditional ACID guarantees, usually via multi-master replication with “latest write wins” conflict resolution. BASE isn’t worth dismissing outright — it has real uses for high-volume data where staleness is tolerable.

But Google’s own Jeff Shute put the cost bluntly: “we find developers spend a significant fraction of their time building extremely complex and error-prone mechanisms to cope with eventual consistency and handle data that may be out of date. We think this is an unacceptable burden to place on developers and that consistency problems should be solved at the database level.” For critical state — a financial transaction, a leader election, a lock — the position is unambiguous: correctness is not a place to economize.

There’s a deeper theoretical wall behind all of this, one worth stating plainly and then moving past: the FLP impossibility result proves that no asynchronous consensus algorithm can guarantee progress in the presence of an unreliable network — in the worst case, a purely asynchronous system can be forced to never decide.

Real systems route around this not by beating the theorem but by accepting its terms: they guarantee safety always (never two conflicting decisions) and liveness (actually making progress) only when enough replicas and network connectivity are healthy, with randomized backoff to prevent competing proposers from livelocking each other forever — a failure mode the literature calls dueling proposers, and one every leader-election implementation has to design against explicitly.

The Mechanism That Actually Works: Quorums

Paxos boils down to one intuition worth internalizing precisely because it recurs everywhere: a quorum is an overlapping majority. If every decision requires agreement from more than half the replicas, then any two decisions — proposed at different times, possibly by different, competing proposers — must share at least one replica between their two majorities.

That shared replica has already committed to one answer and, by protocol, refuses to agree to a conflicting one. Split-brain doesn’t become merely unlikely; it becomes mathematically impossible, for as long as the quorum arithmetic holds.

Paxos itself, though, isn’t that useful on its own — all it does is let a group agree on one value, one time. The systems people actually build sit a layer above:

Then there’s the replica-count math almost nobody’s intuition gets right on the first try. A majority-quorum system of 2f+1 replicas tolerates f failures: three replicas survive one failure, five survive two. Since most downtime is planned maintenance, three replicas already let you take one down for upkeep without an outage — but if an unplanned failure lands during that maintenance window, the system goes fully unavailable, which is why production-critical groups typically run five.

Here’s the counterintuitive part worth spelling out explicitly: adding a sixth replica can reduce availability, not improve it. Six replicas need a quorum of four, and now only 33% of the group can be unavailable before you lose quorum — down from 40% with five replicas needing three. More redundancy, applied carelessly, subtracts fault tolerance.

The same logic governs where replicas live: spread across five datacenters, one per group, losing a single datacenter still leaves a spare in every remaining replica; add a sixth replica to any single one of those datacenters and that datacenter’s failure now takes out two spares at once. Geography and headcount both have to be reasoned about together, or the math quietly works against you.

Performance isn’t a lost cause either, though the “consensus is too slow” folklore is worth debunking directly. Multi-Paxos elects a stable leader so that, once a term is established, reaching agreement costs one network round trip instead of two full phases — the same pattern Raft and Zab both use for the same reason.

Quorum leases let a subset of replicas serve strongly-consistent reads locally, without a consensus round trip, at the cost of slightly slower writes to that leased data — a good trade wherever reads vastly outnumber writes, which is most systems.

And because every acceptor must durably log its promises before replying (so a crash-and-restart can’t violate a guarantee it already made), disk write latency, not network latency, is often the real performance ceiling: at roughly 10ms per synchronous small write, a naive implementation caps out around 100 consensus operations per second, before batching and pipelining multiple proposals into the same round trip — the same “keep the pipe full” trick TCP uses — bring real throughput up by orders of magnitude.

Applied: The Distributed Cron

All of this theory turns into a worked example every ops engineer recognizes on sight: the humble cron job, distributed.

Single-machine cron doesn’t survive the datacenter — a service on 1,000 machines can’t tolerate cron living on just one of them. So Google decoupled the scheduler from any specific machine and gave it exactly the leader/follower Paxos structure described above in the abstract: a leader owns the schedule and is the only replica allowed to talk to the datacenter scheduler, while followers shadow every state change so any one of them can take over within the one-minute failover budget the design targets.

Two Paxos-synchronized checkpoints bracket every single job launch, and the reason there are exactly two is worth sitting with: before launch, the leader announces “I’m about to launch job X, scheduled at time T” to a quorum, so exactly one leader ever owns that decision; after launch, it announces completion, so a leader that dies mid-launch leaves the followers able to tell, unambiguously, whether the launch actually happened.

Without that second checkpoint, a promoted follower has no way to distinguish “the old leader launched this and then died” from “the old leader died before launching this” — and guessing wrong in either direction is bad in a different way.

The mechanism that makes “unsure” resolvable at all is precomputed, launch-time-stamped job names: if a new leader can look up whether a name already exists on the datacenter scheduler, it can distinguish a genuine gap from a launch that already happened, and it doesn’t need to touch the scheduler at all just to check.

The storage design underneath is a small masterclass in matching guarantees to actual risk: Paxos logs and periodic state snapshots both live on each replica’s local disk (three replicas, three copies) — but only the snapshots are also backed up to a distributed filesystem, because losing all three local disks simultaneously is rare enough, and the logs since the last snapshot are cheap enough to lose, that paying the write-latency cost of durable-logging every log entry to a distributed store wasn’t worth it.

The final wrinkle is the ? crontab field: instead of every team’s “run daily at midnight” job actually firing at midnight — a thundering herd of thousands of jobs launching in the same second — the cron system hashes each job’s configuration across its scheduling window and picks a stable, spread-out second for it, without the job owner ever noticing.

Validated: The Theory Got Field-Tested, Publicly

Google’s own advice is to use “formally proven and tested thoroughly” consensus implementations — and the decade’s most visible confirmation of why that qualifier matters came from outside Google entirely.

Kyle Kingsbury’s Jepsen testing project spent the years since 2016 methodically partition-testing production consensus systems — MongoDB, etcd, CockroachDB, Redis, and dozens more — and repeatedly found real, exploitable consistency violations in systems that advertised strong guarantees.

Jepsen’s most useful public service wasn’t proving the theorem right. It was proving how easy it still is, in 2026, to implement consensus incorrectly even when everyone involved knows the theory cold.

The Site Reliability Workbook, Google’s 2018 hands-on companion, doesn’t add new consensus theory — but its case-study format is itself evidence for the same thesis. Real customers (Evernote, The Home Depot, The New York Times) narrate what broke when they tried to apply Google’s SRE practices to their own infrastructure.

The consensus-shaped bugs — accidental split-brain, ad-hoc leader election via database row locks, “we’ll just add a distributed lock” as an afterthought — show up in those narratives precisely where a team reached for something homegrown instead of an off-the-shelf, formally verified implementation.

Ten Years On: etcd Everywhere, and the Bills That Came Due

The decade’s headline: Google’s exotic Chubby niche became etcd, running under essentially every Kubernetes cluster on Earth — Raft in place of Paxos, but the same overlapping-majority mathematics underneath. The theory held; the operational lessons arrived the hard way, and they arrived from consensus’s own dependencies, not consensus itself:

• Roblox, October 28–31, 2021 — 73 hours down. Two compounding root causes in the consensus-adjacent stack: a Consul streaming feature created contention under high load, and a BoltDB freelist bug — its freelist was stored as an array, so every read/write forced a linear scan that got more expensive as the freelist grew, a defect fixed years earlier in bbolt but never backported to the BoltDB fork Consul depended on. The outage’s sharpest lesson runs through all of this: the systems you depend on to agree are themselves distributed systems, with their own failure modes you need to understand before you depend on them — the advice to monitor whether a leader exists, how often it changes, and whether the transaction number is still climbing would have surfaced this one far earlier than 73 hours in.
• The cron-design questions above became Kubernetes CronJob semantics almost verbatim: concurrencyPolicy (Allow/Forbid/Replace — the modern, declarative answer to “what happens if it runs twice?”), timeZone (stable since Kubernetes 1.27, ending a decade of UTC-surprise bugs), and Jenkins’ H symbol as the ? field’s direct spiritual descendant.

The deeper 2026 observation: consensus moved down the stack. It’s infrastructure you assume now (etcd, Raft libraries, managed control planes) rather than code you write — which is exactly why AI-assisted incident diagnosis struggles with it in a specific, instructive way.

A 2026 root-cause-analysis approach like RC-LLM fuses trace, metric, and log signals to reason about causal chains, not just temporal correlation — and it’s genuinely useful for a split-brain incident that matches a pattern the model has seen before (a Roblox-shaped BoltDB freelist bloat, say). But the field’s own honest finding is that this accuracy drops off sharply for genuinely novel failure modes — and split-brain-adjacent incidents are disproportionately novel, precisely because they only happen when someone skipped the formally-verified primitive and improvised.

The practical implication for 2026 on-call: an AI-assisted investigator is a good first pass at “is this the Roblox bug again,” and a poor substitute for the human judgment this always demanded — reading the actual Paxos/Raft term-change counter, not just the symptom. The distributed tracing this kind of diagnosis leans on is exactly what Practical OpenTelemetry’s look at the Collector and OTLP pipeline covers from the instrumentation side — you can’t fuse trace and log signals you never collected.

The ticking bomb from the opening warning is still there in 2026. It’s just wearing a Helm chart now, and increasingly, an AI assistant is the first one to look at it.

Next: Part 10: Never Trust a Backup You Haven’t Restored — pipelines and data integrity.

References

• Google SRE Book — Managing Critical State: Distributed Consensus for Reliability and Distributed Periodic Scheduling with Cron
• The Site Reliability Workbook
• Jepsen — distributed systems safety analysis
• Roblox — Return to Service 10/28-10/31/2021
• Kubernetes CronJob reference
• RC-LLM: Root Cause Analysis Method Based on Large Language Models with Residual Connection Structures