Whitepapers

15 items

MapReduce: Simplified Data Processing on Large Clusters

30mintermediate

Kafka: A Distributed Messaging System for Log Processing

30mintermediate

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

25mintermediate

distributed-systemscap-theoremconsistencyavailabilitypartition-tolerancedatabase-theoryintermediate

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

The formal proof that distributed systems must choose between consistency and availability during network partitions

Seth Gilbert, Nancy Lynch|MIT|2002|25 min read

View Original Paper

Summary

The CAP theorem proves that any distributed data store can provide only two of three guarantees: Consistency (every read receives the most recent write), Availability (every request receives a response), and Partition tolerance (the system continues operating despite network failures). Since network partitions are inevitable in distributed systems, the real choice is between consistency and availability during partitions. This fundamental result shapes every distributed database design.

Key Takeaways

Impossibility Result

CAP is not a guideline—it's a mathematical proof. No algorithm exists that can provide all three properties simultaneously. This isn't a limitation of current technology; it's a fundamental constraint of distributed computing.

Partition Tolerance is Mandatory

Network partitions will happen: switches fail, cables are cut, datacenters lose connectivity. Any system spanning multiple nodes must handle partitions. The real choice is CP (consistency) or AP (availability) during partitions.

Consistency Definition Matters

CAP's "consistency" means linearizability—the strongest form. Weaker consistency models (eventual, causal) can provide better availability. Many "AP" systems offer useful consistency guarantees short of linearizability.

In 2000, Eric Brewer presented a conjecture at the ACM Symposium on Principles of Distributed Computing (PODC). He claimed that any shared-data system can have at most two of three desirable properties:

Consistency (C): Every read receives the most recent write or an error. All nodes see the same data at the same time. This is linearizability—operations appear to happen instantaneously at some point between invocation and response.

Availability (A): Every request to a non-failing node receives a response, without guarantee that it contains the most recent write. The system remains operational.

Partition Tolerance (P): The system continues to operate despite arbitrary message loss or failure of part of the system. Network splits don't cause the system to fail entirely.

Brewer's claim was based on practical experience building large-scale systems at Inktomi. Two years later, Gilbert and Lynch formalized the conjecture and proved it mathematically.

The CAP Triangle

Summary

Key Takeaways

Impossibility Result

Partition Tolerance is Mandatory

Consistency Definition Matters

Availability Definition Matters

CAP's "availability" means every non-failing node must respond. A system that responds from 2 of 3 nodes during partition is technically "unavailable" by CAP but highly available in practice.

Partitions are Temporary

Partitions eventually heal. During partition, choose C or A. After partition heals, reconcile. Many systems detect partitions and dynamically switch strategies.

CAP is Per-Operation

Different operations can make different tradeoffs. User sessions might be AP (always accessible) while financial transactions are CP (always consistent). One system can have both.

Deep Dive

Availability (A): Every request to a non-failing node receives a response, without guarantee that it contains the most recent write. The system remains operational.

Partition Tolerance (P): The system continues to operate despite arbitrary message loss or failure of part of the system. Network splits don't cause the system to fail entirely.

Brewer's claim was based on practical experience building large-scale systems at Inktomi. Two years later, Gilbert and Lynch formalized the conjecture and proved it mathematically.

The CAP Triangle

Trade-offs

Aspect	Advantage	Disadvantage
Consistency Priority (CP)	Never returns stale or conflicting data; simplifies application logic; critical for financial/inventory systems	Unavailable during partitions; higher latency due to coordination; some operations will fail
Availability Priority (AP)	Always responds to requests; better user experience; handles partitions gracefully	May return stale data; requires conflict resolution; application must handle inconsistency
Strong Consistency Models	Easiest to reason about; matches single-server semantics; no surprises for developers	Requires coordination (latency cost); limits throughput; harder to scale globally
Eventual Consistency	Highest availability and lowest latency; scales globally; partition-friendly	Harder to reason about; conflict resolution complexity; may expose inconsistency to users
Tunable Consistency	Flexibility to match requirements per-operation; best of both worlds when used correctly	More complex to configure; easy to misconfigure; harder to understand system behavior

Premium Content

distributed-systemscap-theoremconsistencyavailabilitypartition-tolerancedatabase-theoryintermediate

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

The formal proof that distributed systems must choose between consistency and availability during network partitions

Seth Gilbert, Nancy Lynch|MIT|2002|25 min read

View Original Paper

Summary

Key Takeaways

Impossibility Result

Partition Tolerance is Mandatory

Consistency Definition Matters

Availability (A): Every request to a non-failing node receives a response, without guarantee that it contains the most recent write. The system remains operational.

Partition Tolerance (P): The system continues to operate despite arbitrary message loss or failure of part of the system. Network splits don't cause the system to fail entirely.

Brewer's claim was based on practical experience building large-scale systems at Inktomi. Two years later, Gilbert and Lynch formalized the conjecture and proved it mathematically.

The CAP Triangle

Summary

Key Takeaways

Impossibility Result

Partition Tolerance is Mandatory

Consistency Definition Matters

Availability Definition Matters

CAP's "availability" means every non-failing node must respond. A system that responds from 2 of 3 nodes during partition is technically "unavailable" by CAP but highly available in practice.

Partitions are Temporary

Partitions eventually heal. During partition, choose C or A. After partition heals, reconcile. Many systems detect partitions and dynamically switch strategies.

CAP is Per-Operation

Different operations can make different tradeoffs. User sessions might be AP (always accessible) while financial transactions are CP (always consistent). One system can have both.

Deep Dive

Availability (A): Every request to a non-failing node receives a response, without guarantee that it contains the most recent write. The system remains operational.

Partition Tolerance (P): The system continues to operate despite arbitrary message loss or failure of part of the system. Network splits don't cause the system to fail entirely.

Brewer's claim was based on practical experience building large-scale systems at Inktomi. Two years later, Gilbert and Lynch formalized the conjecture and proved it mathematically.

The CAP Triangle

Trade-offs

Aspect	Advantage	Disadvantage
Consistency Priority (CP)	Never returns stale or conflicting data; simplifies application logic; critical for financial/inventory systems	Unavailable during partitions; higher latency due to coordination; some operations will fail
Availability Priority (AP)	Always responds to requests; better user experience; handles partitions gracefully	May return stale data; requires conflict resolution; application must handle inconsistency
Strong Consistency Models	Easiest to reason about; matches single-server semantics; no surprises for developers	Requires coordination (latency cost); limits throughput; harder to scale globally
Eventual Consistency	Highest availability and lowest latency; scales globally; partition-friendly	Harder to reason about; conflict resolution complexity; may expose inconsistency to users
Tunable Consistency	Flexibility to match requirements per-operation; best of both worlds when used correctly	More complex to configure; easy to misconfigure; harder to understand system behavior

Whitepapers

MapReduce: Simplified Data Processing on Large Clusters

Kafka: A Distributed Messaging System for Log Processing

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Bitcoin: A Peer-to-Peer Electronic Cash System

In Search of an Understandable Consensus Algorithm (Raft)

TAO: Facebook's Distributed Data Store for the Social Graph

The Google File System

The Log-Structured Merge-Tree (LSM-Tree)

The Chubby Lock Service for Loosely-Coupled Distributed Systems

Spanner: Google's Globally Distributed Database

Bigtable: A Distributed Storage System for Structured Data

Scaling Memcache at Facebook

Large-scale cluster management at Google with Borg

The Next 700 Programming Languages

The Part-Time Parliament

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Summary

Key Takeaways

Impossibility Result

Partition Tolerance is Mandatory

Consistency Definition Matters

The Conjecture: Brewer's Original Claim

The CAP Triangle

Premium Content

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Summary

Key Takeaways

Impossibility Result

Partition Tolerance is Mandatory

Consistency Definition Matters

The Conjecture: Brewer's Original Claim

The CAP Triangle

Premium Content