- Choose CA - You can get CA (consistency, availability) for a database service running within a datacenter. Use DRBD with MySQL. Then use asynchronous replication to a remote datacenter to survive the loss of a datacenter. You don't get CA between datacenters in this setup. Others have written about the ability to get CA within a datacenter.
- Repeatable DBMS errors - I call these queries of death. I notice about one per year. MySQL is remarkably stable if you are careful about the features that you use. New SQL must never run first on a master.
- Unrepeatable DBMS errors - These are also infrequent with MySQL but much more frequent than repeatable errors. These are usually impossible to distinguish from intermittent errors caused by hardware and other system software.
- P of the CAP theorem is a rare event - I don't have numbers but I don't agree with this for services running across a WAN. Additionally, there are other reasons to sacrifice P. Many applications cannot afford the latency required for strong consistency.
I am certainly not an expert on Paxos, but it is the way to get strong consistency for a database service running across a WAN. This costs one or two round trips depending on whether the commit coordinator migrates between servers. In theory we should be able to afford the overhead of 100 milliseconds to 200 milliseconds for latency sensitive services. We get a lot in return.
But applications and existing database servers can make this difficult to achieve. Many applications are conversational (request, think, request, think, commit -- substitute network latency for 'think'). Many database servers have one resource, the database log, for which Paxos must be run. This guarantees that the commit coordinator will frequently migrate and commit will require two round trips. Even when the log isn't a problem, there will be performance problems for rows that are frequently updated from all locations.
This will change in the future. Servers that are optimized for OLTP (no conversational transactions) will be designed. VoltDB is doing this today (disclaimer, a family member works there). Servers that are optimized for strong consistency across a WAN are also getting built and will become more popular over time.
I think that MySQL can take part in that future (strong consistency across a WAN), but that requires a new storage engine.