The CAP Theorem Is Not a Theorem

After reading the attempted proof of the CAP conjecture [Lynch], I have come to the same conclusion as Mark Burgess [Burgess]. He writes:

Brewer's original conjecture has not been proven with mathematical rigour -- indeed, the formulation in terms of C, A and P is too imprecise for that to happen. So the status of CAP as a theorem is something of an urban myth [...].

[...]

Also, as a piece of scientific work, the paper is somewhat difficult to understand today, because it builds on a very particular set of unstated assumptions, jargon and mode of thinking that was rooted in the time of its writing. Moreover, it provides no precise definitions of any of the quantities referred to, particularly the much-discussed "P" ("tolerance" of packet loss). Part of the problem is that the conjecture is about network fault tolerance, but it never models the network at all.

Despite this, CAP is not useless, quite the contrary. It has spawned numerous discussions on the limitations of the availability and consistency that distributed services can provide.

I would like to see more mathematical rigor in computers science in general and for databases in particular. Data storage is a field where mathematics can be truly helpful. More on that some other time.

[Lynch] Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, Nancy Lynch and Seth Gilbert, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.

[Burgess] Deconstructing the `CAP theorem' for CM and DevOps, Mark Burgess, http://markburgess.org/blog_cap.html