Eric Brewer presented CAP in a keynote at the PODC. The best slides are on page 4. With XA you forfeit partitions and get CA (consistency + availability). With majority protocols you forfeit availability and get CP (consistency + partition tolerance). XA == CA is easy for me to remember and then I know that majority protocols provide CP.
CAP was proved in a paper by Gilbert and Lynch. This paper defines availability and partition tolerance as used by CAP.
- availability - every request received by a non-failing node must result in a response
- partition tolerance - The network will be allowed to lose arbitrarily many messages sent from one node to another. Every node receiving a request from a client must respond, even though arbitrary messages that are sent may be lost.
What does this have to do with MySQL? I think we will be talking about CAP much more in the future. I found an interesting presentation that explained current MySQL solutions (DRBD, master-slave, master-master, NDB/Cluster) in terms of CAP, but it didn't have enough notes to explain the content.