The CAP theorem states that one can only have two of consistency, availability, and tolerance to network partitions at the same time. In distributed systems, network partitioning is inevitable and must be tolerated, so essential CAP means that we cannot have both consistency and 100% availability. This means if the network is broken, your database won’t work. However, we do get to pick the definition of “won’t work”. It can either mean down (unavailable) or inconsistent (stale data).
The notion of CAP theorem was first started by Eric Brewer. In his speech in the year 2000 he said “…as applications become more web-based we should stop worrying about data consistency, because if we want high availability in these new distributed applications, then guaranteed consistency of data is something we cannot have,…”.
Brewer’s idea where formally proved by Seth Gilbert and Nancy Lynch in 2002. “…It is impossible to implement a read/write data object that guarantees of availability and atomic consistency, in all fair executions (including those in which messages are lost)”.
References
Cooper, B.F. (2008) “PNUTS: Yahoo!’s Hosted Data Serving Platform,” Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288
On Distributed Consistency http://blog.mongodb.org/post/475279604/on-distributed-consistency-part-1
