Two PhD Students, Cheap PCs, and a Philosophy That Changed Computing
In 1998, Larry Page and Sergey Brin published a paper describing their approach to indexing the web. They could not afford enterprise servers, so they bought consumer PCs from Fry's Electronics and connected them with cheap networking equipment. The machines crashed constantly. Disks failed. Network links dropped.
Their insight was not to build more reliable hardware. It was to write software that expected the hardware to fail. Do not prevent crashes; design so they do not matter. Replicate data so losing one machine loses nothing. Detect failures automatically and route around them. This philosophy, design for failure rather than against it, became the founding principle of modern distributed systems. Google did not succeed because it had better hardware. It succeeded because it assumed hardware would fail and built accordingly.
The single most important mindset shift in distributed systems: failure is not an edge case to prevent. It is the default state to design around.
The CAP Theorem (2000)
At the ACM Symposium on Principles of Distributed Computing in 2000, Eric Brewer from UC Berkeley dropped a conjecture that became the most debated result in distributed systems. In any networked system, you can guarantee at most two of three properties: Consistency (every read sees the most recent write), Availability (every request gets a response), and Partition tolerance (the system works even when network links between nodes fail).
Gilbert and Lynch formally proved Brewer's conjecture as a theorem in 2002. The proof relies on a simple observation: network partitions are inevitable in any real distributed system. Cables get cut. Switches fail. Cloud availability zones lose connectivity. Since you cannot eliminate partitions, you are really choosing between consistency and availability when a partition occurs.
CP vs AP: Real Examples
CP systems (Consistency + Partition tolerance) choose to return errors or refuse service rather than serve potentially stale data. If the system cannot confirm it has the latest data, it says so. Examples include:
HBase: returns errors on partition rather than risk stale reads
Zookeeper: used for distributed coordination, must be consistent. A stale leader election could corrupt your whole cluster.
Traditional RDBMS with synchronous replication: the replica must confirm the write before the primary acknowledges it
AP systems (Availability + Partition tolerance) choose to serve potentially stale data rather than refuse requests. Examples include:
Cassandra: always accepts writes and reads, reconciles later. Shopping carts must always be writable.
DNS: serves cached records even if the authoritative server is unreachable. Stale but available beats accurate but unavailable.
CouchDB: multi-master with conflict resolution on sync
The Real Lesson: CAP is About Partition Behavior
Brewer himself corrected the most common misreading of CAP in a 2012 retrospective. Most people treat it as a permanent architectural choice: 'we are a CP system.' That is wrong. During normal operation with no partitions, you can have all three. The real question is: what do you do during the 0.1% of the time when a partition actually occurs? Do you serve stale data (AP) or refuse requests (CP)? And critically: how quickly do you recover full consistency once the partition heals?
Modern distributed database design treats CAP as a spectrum, not a binary. You might serve eventually consistent data for reads but require strong consistency for financial writes. You might allow AP behavior for user preference data but CP behavior for inventory. The sophisticated interview answer is not picking a side. It is identifying which operations in your system can tolerate staleness and which cannot, then designing each accordingly.
Further Reading
Brewer (2000): 'Towards Robust Distributed Systems', the original keynote
Gilbert & Lynch (2002): 'Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services', the formal proof
Brewer (2012): 'CAP Twelve Years Later: How the Rules Have Changed'
Martin Kleppmann (2015): 'A Critique of the CAP Theorem', a nuanced view on its limitations
The Consistency Spectrum: From Linearizable to Eventual
CAP's binary C vs A framing is too coarse for real system design. Consistency is a spectrum with multiple well-defined levels. Linearizability (also called atomic consistency) is the strongest: every operation appears to take effect instantaneously at some point between its invocation and completion, and every client sees the same real-time ordering. Sequential consistency relaxes the real-time requirement: all processes see operations in the same global order, but that order can lag behind real time. Causal consistency guarantees that causally related operations are seen in causal order, but concurrent operations can be seen in different orders by different nodes. Eventual consistency only guarantees that replicas will converge if updates stop, with no time bound.
Linearizability: single-copy semantics globally. Required for distributed locks, leader election, counters. Very expensive.
Sequential consistency: all nodes agree on a global ordering. Less expensive than linearizability, still strong.
Causal consistency: if A happened-before B, everyone sees A before B. Concurrent events can be seen in any order.
Read-your-writes consistency: after you write, you always read your own write. Critical for user-facing apps.
Eventual consistency: all replicas converge eventually. No guarantees on timing. Acceptable for non-critical reads.
PACELC: The Model That Adds Latency to CAP
CAP only reasons about partitions. Daniel Abadi's PACELC theorem extends it: during a Partition (P), you choose between Availability (A) and Consistency (C). Else (E) during normal operation, you choose between Latency (L) and Consistency (C). This is more useful because partitions are rare. Most of the time you are choosing how much consistency to sacrifice for lower latency. Cassandra is PA/EL: it stays available during partitions and trades consistency for low latency during normal operation. Spanner is PC/EC: it refuses availability during partitions and accepts higher latency in exchange for strong consistency always.
DynamoDB: PA/EL by default, configurable per request with strongly-consistent read option
Cassandra: PA/EL. Tunable with quorum reads/writes but defaults favor availability and latency
HBase: PC/EC. Built for strong consistency, sacrifices availability and latency
CockroachDB: PC/EC. Serializable isolation, higher latency than eventually consistent alternatives
MongoDB: configurable. Default is PC/EC with majority write concern, can be tuned toward EL
What Interviewers Test About CAP and Consistency
CAP questions are a filter for systems thinking maturity. Junior candidates recite the definition. Senior candidates discuss which property their specific system can afford to trade and under what conditions. The most impressive interview answers tie CAP choices to business requirements: 'payment confirmations require linearizability because a lost update is a financial error, but recommendation feeds can tolerate eventual consistency because a stale recommendation has no business impact.'
Know: why you cannot eliminate partition tolerance (P) in a real distributed system and must choose A or C
Know: the difference between consistency in CAP (all nodes see the same data) and consistency in ACID (data meets invariants)
Know: split-brain scenario - two nodes each think they are the primary. What breaks? How to prevent with leader election.
Know: how quorum reads and writes work and how R+W>N gives you strong consistency in a distributed setting
Red flag: treating CAP as a permanent architectural label instead of a behavior-under-partition specification
The Consistency Spectrum: From Linearizable to Eventual
CAP's binary C vs A framing is too coarse for real system design. Consistency is a spectrum with multiple well-defined levels. Linearizability (also called atomic consistency) is the strongest: every operation appears to take effect instantaneously at some point between its invocation and completion, and every client sees the same real-time ordering. Sequential consistency relaxes the real-time requirement: all processes see operations in the same global order, but that order can lag behind real time. Causal consistency guarantees that causally related operations are seen in causal order, but concurrent operations can be seen in different orders by different nodes. Eventual consistency only guarantees that replicas will converge if updates stop, with no time bound.
- Linearizability: single-copy semantics globally. Required for distributed locks, leader election, counters. Very expensive.
- Sequential consistency: all nodes agree on a global ordering. Less expensive than linearizability, still strong.
- Causal consistency: if A happened-before B, everyone sees A before B. Concurrent events can be seen in any order.
- Read-your-writes consistency: after you write, you always read your own write. Critical for user-facing apps.
- Eventual consistency: all replicas converge eventually. No guarantees on timing. Acceptable for non-critical reads.
PACELC: The Model That Adds Latency to CAP
CAP only reasons about partitions. Daniel Abadi's PACELC theorem extends it: during a Partition (P), you choose between Availability (A) and Consistency (C). Else (E) during normal operation, you choose between Latency (L) and Consistency (C). This is more useful because partitions are rare. Most of the time you are choosing how much consistency to sacrifice for lower latency. Cassandra is PA/EL: it stays available during partitions and trades consistency for low latency during normal operation. Spanner is PC/EC: it refuses availability during partitions and accepts higher latency in exchange for strong consistency always.
- DynamoDB: PA/EL by default, configurable per request with strongly-consistent read option
- Cassandra: PA/EL. Tunable with quorum reads/writes but defaults favor availability and latency
- HBase: PC/EC. Built for strong consistency, sacrifices availability and latency
- CockroachDB: PC/EC. Serializable isolation, higher latency than eventually consistent alternatives
- MongoDB: configurable. Default is PC/EC with majority write concern, can be tuned toward EL
What Interviewers Test About CAP and Consistency
CAP questions are a filter for systems thinking maturity. Junior candidates recite the definition. Senior candidates discuss which property their specific system can afford to trade and under what conditions. The most impressive interview answers tie CAP choices to business requirements: 'payment confirmations require linearizability because a lost update is a financial error, but recommendation feeds can tolerate eventual consistency because a stale recommendation has no business impact.'
- Know: why you cannot eliminate partition tolerance (P) in a real distributed system and must choose A or C
- Know: the difference between consistency in CAP (all nodes see the same data) and consistency in ACID (data meets invariants)
- Know: split-brain scenario - two nodes each think they are the primary. What breaks? How to prevent with leader election.
- Know: how quorum reads and writes work and how R+W>N gives you strong consistency in a distributed setting
- Red flag: treating CAP as a permanent architectural label instead of a behavior-under-partition specification