Distributed Systems Basics: CAP, Consensus, and Eventual Consistency

Matt George

Fractional CTO · Founder of Injuria.ai

A program running on one computer lives in a tidy world. Memory is reliable, operations happen in order, and if the machine dies, the whole program dies with it, cleanly. The moment you spread that program across several machines, for scale or for resilience, you leave that tidy world behind. Parts of the system can fail while other parts keep running, messages can be slow or lost, and two nodes can hold different ideas about what is true at the same instant. Distributed systems are the study of building something dependable on top of that mess, and the core ideas are worth knowing even if you never design one from scratch.[7]

Why distribution is genuinely hard

The root difficulty is partial failure. On a single machine, a component either works or the machine is down. In a distributed system, one node can fail while the rest carry on, and worse, the healthy nodes often cannot tell the difference between a peer that has crashed and a peer that is simply slow or unreachable. A request that got no reply might mean the work never happened, or it might mean the work happened and the confirmation got lost.[8] You cannot always tell which.

On top of that, the network itself is unreliable. Messages arrive late, out of order, twice, or never. There is a well known list called the fallacies of distributed computing, cataloging the comfortable assumptions that quietly ruin systems, starting with "the network is reliable" and "latency is zero."[1] Every hard problem in the field traces back to the fact that those assumptions are false. It is worth adding one failure mode most introductions skip: The fail-stop model explicitly assumes that failures are detectable by other nodes; nodes crashing or going silent without detectability is known as the crash or fail-silent model. A nastier world exists, Byzantine failure, where a node lies or returns corrupted data, whether from a bug, memory corruption, or an attacker. Tolerating that requires entirely different and more expensive algorithms, which is why most ordinary systems simply assume it away and blockchains, which cannot, pay dearly for it.[9]

The CAP theorem, stated correctly

The CAP theorem is the most cited and most misquoted idea in the field. It concerns three properties, and the formal definitions matter more than the casual ones. Consistency here means linearizability, the illusion of a single up-to-date copy. Availability means every request to a non-failing node gets a non-error response, note the "non-failing," because a crashed node is not expected to answer. Partition tolerance means the system keeps working when the network drops messages between nodes.[2]

The popular version says "pick two of three." That phrasing is misleading. In any real distributed system, network partitions are not optional, they will happen, so partition tolerance is not a choice you get to decline. What the theorem really says is narrower and more useful: when a partition is happening, and only then, you must choose between consistency and availability.[2][10] You can refuse to answer until you are sure your data is current, sacrificing availability, or answer with possibly stale data, sacrificing consistency.[2]

Even that is not the whole story, and the honest extension is worth knowing. The PACELC principle points out that even when there is no partition, a system still trades latency against consistency: keeping every copy perfectly in sync on every write costs round trips and therefore time.[3] CAP describes the trade-off during a failure. PACELC reminds you there is a quieter trade-off running the rest of the time too, which is why "is your database consistent" is never a yes or no question.

Consistency is a spectrum, not a switch

Outside CAP's strict definition, consistency in practice is a range of models, each a different promise about what a reader can expect to see. Strong consistency behaves as if there were a single copy: once a write succeeds, every later read everywhere sees it. It is the easiest model to reason about and the most expensive to provide, because the nodes must coordinate on every operation. Eventual consistency makes a weaker promise: if writes stop, all copies will converge, but for a while different nodes may return different answers. In between sit models like read-your-writes, which at least guarantees you see your own changes.

The practical point is that stronger consistency costs latency and availability, and weaker consistency buys speed and resilience at the price of temporary disagreement. A bank balance wants strong guarantees. A count of likes on a post can be eventually consistent and nobody is harmed if it is briefly off by one. The real engineering question, once you give up global strong consistency, is how to reconcile conflicting writes, and the field has concrete answers: last-write-wins (simple and lossy), vector clocks (which detect concurrent edits), and conflict-free replicated data types, or CRDTs, data structures mathematically designed so that independent updates always merge without conflict.[6][10] Those are the tools that make "eventually" actually converge.

Consensus: agreeing on a single truth

Many systems need a group of machines to agree on one value or one ordering of events, even though some may fail and the network may misbehave. That problem is consensus, and it is the beating heart of reliable distributed storage. The first widely studied solution was Paxos, described by Leslie Lamport, which is correct and notoriously hard to understand and implement.[4] Raft came later, designed explicitly to be understandable, and it has become the common choice.[5] The rough idea in both is that the nodes elect a leader, the leader proposes each change, and a change is committed only once a majority, a quorum, has acknowledged it. Requiring a majority is what lets the system tolerate a minority of nodes failing while never committing two conflicting decisions. Systems like etcd and Consul run Raft to keep a cluster agreeing on its state.[11]

There is a deeper problem lurking under all of this that is worth naming: time. You cannot trust the physical clocks on separate machines to agree, so you cannot order events by timestamp. Distributed systems instead establish ordering with logical clocks, Lamport timestamps and vector clocks, or, in Google's Spanner, with specially engineered hardware clocks called TrueTime that bound their own uncertainty. "What happened first" is a genuinely hard question when there is no shared now.

Choosing your trade-off on purpose

None of this tells you the right answer, because there is no universally right answer. There is only the trade-off you choose deliberately versus the one that chooses you during an outage. A system that favors consistency will, during a partition, return errors rather than risk serving conflicting data, which is what financial and inventory systems usually want. A system that favors availability will keep serving and reconcile afterward, which is what shopping carts and social feeds usually want.

The failure I have watched sink teams is not choosing wrong. It is not choosing at all, and discovering their system's real behavior for the first time in the middle of an incident. That is the whole practical value of these ideas. You do not need to implement Raft or hand-roll a CRDT to benefit from them. You need them so that when you pick a database, a queue, or a cache, you already know which questions to ask, and so the trade-off is one you made on a quiet afternoon rather than one the network made for you at three in the morning.

Sources (11)
  1. Fallacies of distributed computing (Wikipedia)
  2. CAP theorem (Wikipedia)
  3. PACELC design principle (Wikipedia)
  4. Leslie Lamport, Paxos Made Simple (Microsoft Research)
  5. Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (Raft, USENIX ATC 2014)
  6. Conflict-free replicated data type (Wikipedia)
  7. Ludwik Czaja, Introduction to Distributed Computer Systems (Springer, 2018)
  8. ACM Special Interest Group for Automata and Computability Theory, ACM Special Interest Group in Operating Systems, Association for Computing Machinery, ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 18-20, 1982, Ottawa, Canada (New York : Association for Computing Machine
  9. Kenneth P Birman, Guide to Reliable Distributed Systems (Springer Science & Business Media, 2012)
  10. Vijay K. Garg, Principles of Distributed Systems (Springer, 2011)
  11. Amy Elser, Guide to Reliable Distributed Systems (Springer, 2012)

Recommended reading