CAP Theorem

Consistency guarantees that every read operation receives the most recent write or an error. It provides a linearizable view of the data across all nodes in the system. After a successful write, all subsequent reads—regardless of which node they hit—will reflect that update.

• Mechanism: Often enforced via atomic broadcast protocols or quorum-based read/write operations (e.g., R + W > N).
• Trade-off: Choosing Consistency alongside Partition tolerance (CP) means the system may become unavailable during a network partition to prevent returning stale data.
• Example: A financial ledger system where reading an account balance must always show the result of the last transaction.

Availability guarantees that every request to a non-failing node receives a (non-error) response, without the guarantee that it contains the most recent write. The system remains operational for both reads and writes even during a network partition.

• Mechanism: Achieved by allowing nodes to operate independently, often using techniques like hinted handoff and sloppy quorums.
• Trade-off: Choosing Availability alongside Partition tolerance (AP) means the system may return stale data during a partition to ensure it continues serving requests.
• Example: A social media timeline or a product catalog where high uptime is prioritized over immediate global consistency.

Partition tolerance is the system's ability to continue operating despite an arbitrary number of messages being dropped or delayed between network nodes. A network partition is a break in communication, splitting the system into isolated subgroups.

• Fundamental Constraint: In a distributed system, network partitions are a fact of life, not a choice. The theorem therefore states you must design for Partition tolerance and choose between Consistency and Availability when a partition occurs.
• Mechanism: Systems achieve this through replication and decentralized coordination, often using consensus algorithms or conflict-free data types (CRDTs) for state reconciliation after the partition heals.

The core assertion of the CAP theorem is the impossibility of simultaneously achieving all three guarantees in the presence of a network partition.

• CP Systems: Sacrifice Availability for Consistency. During a partition, nodes on the minority side will stop responding to requests to avoid serving stale data. Examples include ZooKeeper, etcd, and traditional databases using Paxos or Raft for consensus.
• AP Systems: Sacrifice Consistency for Availability. All nodes remain responsive, but may return divergent, stale, or conflicting data. Examples include DynamoDB, Cassandra (with tunable consistency), and Riak.
• CA Systems: Sacrifice Partition tolerance. These are single-node or tightly-coupled clusters that assume a reliable network. They are not truly distributed in the CAP sense. Most single-master relational databases (e.g., a standalone PostgreSQL instance) are CA systems.

The PACELC theorem extends CAP by addressing system behavior both during and in the absence of partitions.

• If a Partition (P) occurs, trade off between Availability and Consistency (as in CAP).
• Else (E), when the system is running normally, trade off between Latency and Consistency.
• This framework more accurately describes real-world system design. For example:
  • Dynamo-style systems are PA/EL: Prioritize Availability if a Partition occurs, and low Latency otherwise, sacrificing some Consistency.
  • BigTable/HBase are PC/EC: Prioritize Consistency if a Partition occurs (become unavailable), and Consistency otherwise, accepting higher Latency for strong guarantees.

Modern distributed databases often provide tunable consistency models, allowing developers to choose the appropriate trade-off per operation.

• Eventual Consistency: A weak consistency model where, if no new updates are made, all replicas will eventually converge to the same state. This is common in AP systems.
• Strong vs. Eventual: The choice is not binary. Systems offer a spectrum (e.g., causal consistency, session consistency).
• Critical Insight: The '2 of 3' formulation is a simplification. In reality, the trade-off is between consistency and availability during a partition. Engineers design for graceful degradation and configurable behavior rather than a fixed, global choice.

A consistency model for distributed systems where, in the absence of new updates, all replicas will eventually converge to the same state. This is the typical choice for AP (Availability & Partition Tolerance) systems under the CAP Theorem, allowing high availability during network partitions at the cost of temporary read inconsistencies. Examples include DNS and many NoSQL databases like Amazon DynamoDB and Apache Cassandra.

A guarantee that any read operation will return the most recent write for a given data item, providing a linearizable view of the data. This is the model chosen for CP (Consistency & Partition Tolerance) systems under the CAP Theorem, ensuring data correctness at the potential cost of availability during a network partition. It is enforced by protocols like Paxos and Raft, and is critical for systems like financial ledgers.

A property of a distributed system enabling it to reach consensus and function correctly even when some components fail or act maliciously (arbitrary or Byzantine faults). While CAP deals with network partitions and non-malicious crashes, BFT addresses a harsher fault model. Practical implementations like PBFT are foundational for blockchain and critical financial systems, extending reliability guarantees beyond CAP's scope.

Data structures designed for distributed systems that guarantee eventual consistency and can be updated concurrently without coordination, automatically resolving conflicts. CRDTs are a practical engineering solution that operates under the AP side of the CAP Theorem, enabling collaborative applications (like Google Docs or distributed counters) where availability is paramount and merges must be deterministic.

An extension of the CAP Theorem that adds the trade-off between Latency and Consistency when the system is Partition-free (Else). It formalizes the idea that even without partitions, distributed systems must choose between low-latency operations and strong consistency. The full formulation is: if Partition (P), choose between Availability (A) and Consistency (C); Else (E), choose between Latency (L) and Consistency (C).

A mechanism for tracking causality and partial ordering of events in a distributed system. They enable the detection of concurrent updates and are crucial for implementing systems that favor availability (AP). When a partition heals, vector clocks help reconcile what happened, identifying whether updates were concurrent (requiring conflict resolution) or causally related, providing a logical foundation for eventual consistency.