December 18, 2013

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

1 comment:

  1. The Roulette wheel as invented by Pascal remained the same for centuries of years}. That all modified in 1842, when Francois and Lois Blanc designed a Roulette wheel with a single zero on it, particularly for King Charles III of Monaco. This was a large deal because of|as a outcome of} adding a zero gave the home a bigger bigger|an even bigger} home edge. The Roulette wheel was invented by a French physicist, inventor, and mathematician named Blaise Pascal. In 1655, Pascal tried to invent a perpetual movement machine. "He says he almost made enough cash to pay for the roulette wheel he had bought 1xbet to excellent his instrument at home before going out 'into the sphere'," remembers Muller.

    ReplyDelete