CAP & Consistency

Consistency, Availability, and Partition tolerance — the three properties in the CAP theorem for distributed data stores.

That a distributed data store can guarantee at most two of consistency, availability, and partition tolerance simultaneously. When a network partition occurs, you must choose between consistency and availability.

Every read returns the most recent write (or an error) — all nodes present the same, up-to-date view of the data. This is the strong/linearizable sense, stricter than the "C" in ACID.

Every request received by a non-failing node returns a non-error response, without a guarantee that it contains the most recent write.

A communication breakdown that splits the cluster so some nodes can't reach others (dropped or delayed messages), while each side may still be running. The system must decide how to behave when nodes can't coordinate.

A model where, if no new updates are made, all replicas eventually converge to the same value. Reads may return stale data for a while, but the system becomes consistent over time.

Because real networks inevitably drop, delay, or reorder messages and nodes fail. A distributed system spanning machines can't avoid partitions, so it must tolerate them — leaving the practical choice between C and A during a partition.

During a partition, a CP system keeps data consistent by refusing requests it can't safely serve (sacrificing availability) — e.g. it won't accept a write it can't replicate to a quorum. An AP system keeps responding on both sides of the partition (sacrificing consistency), serving possibly-stale data and reconciling later. Choice depends on whether stale/conflicting data or downtime is worse for the use case.

CP: ZooKeeper, etcd, HBase, and consensus-based stores that require a quorum — they'd rather be unavailable in a minority partition than serve stale data. AP: Cassandra and DynamoDB (in their default/eventually-consistent modes), which keep serving during partitions and reconcile. Note many systems are tunable per request (e.g. Cassandra consistency levels), so the label depends on configuration.

They're different concepts sharing a letter. CAP's C is about replica consistency — all nodes returning the latest write (linearizability). ACID's C is about transactional integrity — a transaction moving the database from one valid state to another, preserving constraints/invariants. A system can satisfy one without the other.

A model guaranteeing that operations with a cause-effect relationship are seen by everyone in the same order, while concurrent (unrelated) operations may be seen in different orders. Example: everyone sees a reply after the comment it responds to. It's stronger than eventual consistency but weaker (and cheaper/more available) than strong consistency, and often "good enough" for social/collaborative apps.

Session (client-centric) guarantees. Read-your-writes: after you write a value, your subsequent reads reflect it (you never see your own update disappear). Monotonic reads: once you've read a value, you won't later read an older one (time doesn't go backward for you). They give a good user experience over an eventually-consistent store without the full cost of global strong consistency.

Only if there are no partitions — i.e. a single node or a system that assumes a perfectly reliable network, which doesn't exist across machines. In any real distributed system, partitions can occur, so you effectively always tolerate P and trade between C and A. A single-node database is "CA" trivially but isn't distributed/fault-tolerant.

Prefer availability for a shopping cart, social feed, or "likes" counter — showing slightly stale data or merging carts later is better than an error. Prefer consistency for bank balances, inventory reservations, or unique-username registration — serving stale/conflicting data risks double-spending or overselling, so it's better to reject/wait than be wrong.

PACELC states: if there is a Partition, trade between Availability and Consistency; Else (no partition, normal operation), trade between Latency and Consistency. It's more useful because partitions are rare, but the latency-vs-consistency trade-off happens on every request: strong consistency requires cross-node coordination that adds latency even when the network is healthy. So PACELC captures the everyday cost that CAP ignores. Systems are classified e.g. "PA/EL" (Dynamo/Cassandra: available and low-latency) or "PC/EC" (Spanner/etcd: consistent in both cases).

Linearizability is a recency guarantee on single objects: every operation appears to take effect atomically at some point between its start and end, consistent with real-time order — once a write completes, all later reads see it. Serializability is an isolation guarantee on transactions (possibly multi-object): the result is equivalent to some serial order of transactions, but not necessarily the real-time order. Strict serializability combines both (serial order respects real time). Linearizability is about "latest value now"; serializability is about "transactions don't interleave incorrectly."

Consensus (Paxos/Raft) provides linearizable, fault-tolerant agreement by requiring a majority quorum to commit. This makes such systems CP: in a partition, only the side with a majority can make progress; the minority side becomes unavailable (can't elect a leader or commit) rather than serving stale/inconsistent data. So consensus chooses consistency over availability during partitions, and it also incurs latency (round trips to a quorum) even without partitions — the PACELC "EC" cost. It's the backbone of CP stores like etcd/ZooKeeper and of strongly-consistent databases.

Spanner uses Paxos-replicated groups (so it's fundamentally CP — a partitioned minority can't commit) but achieves very high availability through wide replication across zones/regions so a majority is almost always reachable, plus TrueTime: GPS/atomic-clock-backed clocks with bounded uncertainty. TrueTime lets Spanner assign globally-meaningful commit timestamps and briefly wait out the uncertainty interval, providing external consistency (strict serializability) across the globe. It doesn't beat CAP — during a true partition the minority is unavailable — but it minimizes how often that matters and delivers strong consistency with low practical downtime, at the cost of specialized infrastructure and some commit latency.

Use per-operation consistency. Inventory reservation and payment need strong consistency/serializable transactions (avoid overselling and double-charging) — route to a single authoritative region/shard per SKU or use a CP store, accepting higher latency. Product catalog, reviews, recommendations tolerate eventual consistency and can be served from local replicas/caches for low latency (AP). Cart can be highly available with merge-on-conflict (union items). Use idempotency keys for payment retries, sagas for the multi-step order workflow, and read-your-writes for the user's own actions. The art is applying the strictest model only where correctness demands it, keeping the rest fast and available.

Common errors: (1) treating it as "pick any 2" when in practice P is mandatory, so it's really C-vs-A only during partitions; (2) thinking a system is globally "CP" or "AP" when consistency is usually tunable per operation; (3) conflating CAP's C with ACID's C; (4) ignoring that CAP says nothing about the normal (non-partition) case — that's what PACELC adds; (5) using "we're AP/eventually consistent" to excuse ignoring conflict resolution and correctness. CAP is a narrow theoretical result about a single register under partition, not a design methodology.

With N replicas, requiring W acks per write and R replicas per read, W + R > N guarantees read/write sets overlap so reads can observe the latest write (strong-ish consistency). Raising W/R improves consistency but reduces availability (need more replicas reachable) and adds latency; lowering them (e.g. W=1, R=1) maximizes availability/low latency but allows stale reads. During a partition, whether a side can satisfy W/R determines if it stays available. Tuning per operation (strong reads with R high, fast reads with R=1) lets one store behave CP or AP as needed — though quorums alone don't resolve concurrent-write conflicts, which still need versioning/merging.

Consistency is a property of what clients observe about replicated data (e.g. linearizability, eventual, causal) — a guarantee about read/write behavior. Consensus is the mechanism/problem of getting a set of nodes to agree on a single value/order despite failures (solved by Paxos/Raft). Consensus is often the tool used to implement strong consistency (a linearizable replicated log), but consistency is the observable guarantee while consensus is the algorithmic building block. You can have strong consistency backed by consensus, or weak consistency with no consensus (gossip/anti-entropy).

Not really — CAP is about distributed data stores with multiple nodes. A single server has no inter-node partition to worry about; it's either up (consistent and available) or down. CAP's trade-off appears only once data is replicated across machines.

Every read is guaranteed to return the result of the most recent completed write, so all clients see a single, up-to-date view of the data as if there were one copy.

The ability to choose the consistency/availability trade-off per operation rather than for the whole system. For example, Cassandra lets each query specify a consistency level (ONE, QUORUM, ALL) for reads and writes, so critical operations can be strongly consistent while others favor low latency and availability. This lets one database behave more CP or more AP as needed.

A read that returns an outdated value because it hit a replica that hasn't yet received the latest write (replication lag) or an eventually-consistent store mid-convergence. Stale reads are acceptable for many use cases (feeds, counts) but dangerous for others (balances, inventory), which is why consistency models and read routing matter.

CAP availability is a formal property: every request to a non-failing node gets a non-error response, even during a partition. Everyday high availability (measured in "nines" of uptime) is an operational goal about minimizing downtime. A CP system can be highly available in practice (rarely partitioned) yet is "not available" in the CAP sense during a partition because it may reject requests to preserve consistency.

A vector clock is a per-object vector of counters, one per node/replica, incremented on each update. Comparing two versions' vectors reveals their causal relationship: if one dominates the other (all counters ≥), it's strictly newer; if neither dominates, the writes were concurrent and thus conflicting. This lets leaderless/multi-leader systems detect conflicts precisely (rather than blindly picking last-write-wins) and surface conflicting "siblings" for application or CRDT merging. They add metadata overhead and need pruning as membership changes.

2PC provides atomic commit across nodes: a coordinator gathers "prepared" votes then tells all to commit. To preserve atomicity/consistency, participants that have voted must hold locks and wait for the coordinator's decision — if the coordinator or a participant is unreachable (a partition), they block rather than risk diverging. That blocking is a loss of availability, so 2PC chooses consistency over availability during failures, making it CP (and a reason it's avoided in high-availability designs in favor of sagas).

Both require all nodes to agree on a single total order of operations that respects each process's own program order. The difference is real time: linearizability additionally requires that order to respect real-time ordering — if operation A completes before B begins (wall-clock), A must appear before B. Sequential consistency only preserves per-process order, so a read could return a value that's globally consistent but "in the past" relative to real time as long as no single process observes an inconsistency. Linearizability is strictly stronger and is what "strong consistency" usually means; sequential consistency is cheaper but allows stale-looking results across clients.