computer science//distributed systems//CAP theorem

The CAP theorem is an impossibility result about replicated data: when a network partition separates the replicas, each side must choose between **consistency** (every read sees the latest write) and **availability** (every request gets an answer), and it cannot have both. Eric Brewer stated it as a conjecture in 2000 and Gilbert and Lynch proved it in 2002. It is the question to ask of any store a fleet depends on: when the link between the warehouse and the cloud drops, does the local copy keep answering with what it last knew, or does it refuse until it can be sure?

The CAP theorem is an impossibility result about replicated data: when a network partition separates the replicas, each side must choose between consistency (every read sees the latest write) and availability (every request gets an answer), and it cannot have both. Eric Brewer stated it as a conjecture in 2000 and Gilbert and Lynch proved it in 2002. It is the question to ask of any store a fleet depends on: when the link between the warehouse and the cloud drops, does the local copy keep answering with what it last knew, or does it refuse until it can be sure?

A concrete case shows why no third option exists. Two servers hold the table of which robot owns which order. The link between them breaks, and a client asks the first server to assign order 4512. If the server accepts, it may contradict an assignment the second server has just made: available, inconsistent, and two robots may deliver the same order. If it refuses until the link returns, the data stays right and the warehouse waits: consistent, unavailable. The server cannot know what it cannot hear.

The choice is only forced during a partition, and it can differ for each piece of data.

Order ownership and money want consistency; a robot's last reported position or a dashboard can tolerate staleness and want availability. Most of the design work is deciding which data is which.

The P is not optional. A network that never partitions does not exist beyond one machine, so in practice the choice is between CP systems (etcd and the other Raft stores, whose minority side stops answering) and AP systems (many caches and eventually consistent databases, which answer and reconcile later).

Consistency here means linearizability, a stronger property than the C of database transactions, and availability means that every node still running answers. Weaker definitions of either escape the theorem, which is why it is often overstated; it describes the worst moment, and says little about normal operation.

In a fleet the same choice appears on board. A drone that loses the ground station either keeps working on its last assignment (available, possibly in conflict with a reassignment it never heard) or holds position until it reconnects (consistent, idle). How often the link goes is in communication constraints; how the consistent side keeps agreeing among its majority is distributed consensus.