CAP theorem
When data lives on several servers and the link between them breaks, the system can’t both answer every request and show everyone the same data: it must either wait for the link to return or answer from its own, possibly stale, copy. Eric Brewer stated this in 2000; Seth Gilbert and Nancy Lynch proved it in 2002. Brewer later wrote that the “two of three” formula oversimplifies: the choice arises only during a partition.
The letters: C is consistency, everyone sees the same data; A is availability, every request gets an answer; P is partition tolerance, the system keeps working when messages between servers are lost or delayed. Partitions happen on their own, so in practice the choice is between C and A for the duration of a partition.
The common core with Rice’s theorem: while an event hasn’t happened yet, you can’t tell whether it will happen later or never, however long you wait. A server doesn’t know whether a neighbour’s message is lost or late; a program check doesn’t know whether the program will finish or run forever. So the ways out are similar: while time is unbounded, you pick one of two — wait, or answer now at the risk of being wrong; and bounding the time removes the fork itself, because after the limit “never” is already known. The reasons for the impossibility differ: a server lacks information, while a program check has it, the whole code is in front of it, but the answer can’t be computed from it. This comparison is the author’s; there is no single theorem covering both.
Source: Eric Brewer: CAP twelve years later
Read more: Rice's theorem and the link to CAP
Where it appears · 2
- Where to check an AI agent's work · Specs and context
- Rice's theorem in plain words · Specs and context