CAP - Consistency, Availability and Partition-Tolerant

The CAP principle states that in distributed computing when it comes to consistency (C), availability (A) and partition (P) resilience/tolerance you can have only two of the three.

I was recently introduced to this principle and find it rather insightful.  Basically you can't have your cake and eat it too, otherwise (computing) life would be too easy. 

Eric Brewer, a University of California, Berkeley professor and the co-founder and Chief Scientist of Inktomi, in a 2000 Principles of Distributed Computing (PODC) talk, stated it was impossible for distributed web services to guarantee consistency, availability and partition-tolerance.

Consistency.  Think database consistency.  A read after an update should reflect the update.

Availability.  Highly available web services mean every requests should succeed and receive a response.

Partition-tolerance.  This arise out of the desire for fault-tolerance.  The service should be able to function when part of network fails, when a partition between data replicas will still allow the service to operate.

Take, for example, the Amazon S3 service (Simple Storage Service).  Users can upload data to Amazon, much like a simple FTP service, with very high availability and scalability. 

Amazon's S3 guarantees availability and partition-tolerance but does not guarantee consistency.  Data is replicated to many data centers, and requests will continue to succeed even if communication between data centers fail.  However, it is possible that after an upload a download on a different node would fail, because the data has not been replicated to that node.  The service is not consistent.  Amazon describes this as eventually consistent model.

On the other hand, take a service with distributed transactions.  It will be consistent and available, but if the network partitions the service will not function.

Reference: Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, Seth Gilbert and Nancy Lynch

Comments

[Carlos E. Perez]

Thanks for the insight and links!

[tinou]

Hi Carlos,

Anytime...just trying to give back to the community ;-)