The CAP Theorem
Wednesday, March 09, 2011
1:15 PM
The CAP Theorem
The CAP conjecture (Eric Brewer, 2000): any distributed datastore can only exhibit two of the following three properties
Consistency: all nodes have the same view of data. 
(High) Availability: data is instantly available from the system. 
Partitionability: the system continues to respond if messages are lost (due to system or network failure).
Proved to be true by Gilbert and Lynch (2002). 
In the cloud context: 
Very similar to my initial claim about the tension between consistency and concurrency.
Main contribution: cloud datastores can be categorized in terms of the two (of three) properties C,A,P that they exhibit. 
AppEngine is in class CP = Consistency + Partitionability
Only other reasonable cloud class is class AP = Availability + Partionability
We don't want a cloud datastore that loses data (e.g., ¬P)!