Brewer's CAP conjecture is that a networked system cannot be consistent,
available, and partition tolerant.  A long description can be found at

     http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

and a purported "proof" at
 
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.20.1495&rep=rep1&type=pdf

The CAP conjecture, I am convinced, is false and can be proven false.

The counterexample to the conjecture and the flaw in the "proof" is that
each assumes that a system needs to be serializable to be consistent.
Serializability is a sufficient condition for consistency, but is not a
necessary condition.  A counterexample of a system that demonstrates CAP
false has the following characteristics:

   1. The system is transactional, i.e. all updates within a transaction
      are tentative until committed atomically.
   2. Inconsistency can be detected during execution of a transaction so
      that a transaction that would otherwise introduce inconsistency is
      prevented from committing.
   3. Commits are executed in the context of a partition tolerant commit
      algorithm (a transaction is not committed until it has been
      reported as committable to all potential surviving partitions).

The only serious question is whether a system can be both
non-serializable and consistent, and it isn't much of question given a
formal definition of consistency (concurrent transactions can't
overwrite each other, unique constraints must appear unique, etc.).  It
is easier, cheaper, and bullet proof to serialize updates to specific
elements within a transaction than to try to serialize transactions
themselves.  For example, every database record might have a
deterministic resolution agent that actively prevents concurrent update
in an multi-version concurrency control (MVCC) database.

The quintessential problem is that academic computer science has been
conflating the concepts of consistent and serializable for so long that
it has forgotten that they are not the same thing.  If you substitute
"serializable" for "consistent", the CAP conjecture becomes the SAP
conjecture, and is probably true.  So the trick is to be CAP without
being a SAP.

The CAP conjecture has been a theoretical millstone around the neck of
all ACID systems.  Good riddance.

This is the first wooden stake for the heart of the noSQL movement.
There are more coming.

--
Jim Starkey
Founder, NimbusDB, Inc.
978 526-1376