> A trivial system with these properties is one that replicates every update to all available nodes and requires reads to get matching results from at least half of the nodes.

Nope. You haven't thought this through.

One problem is that "all available nodes" is one of those fuzzy concepts that sounds reasonable but is actually impossible to actually do.

Say you send a write to 3 replicas, all of which you think are up. Only one acks the write within 10s. Did the other nodes fail before getting the write? You have no way to know. In the meantime, what do you do with the node that did ack your write? If you tell it to rollback, what happens if the other, "failed" nodes failed after performing the write, but before the ack? Or are they about to ack, if only you wait another 1s?

(2PC can help but there are failure scenarios it can't handle, either. http://en.wikipedia.org/wiki/Two-phase_commit_protocol#Disad...)

Another way to think of the P in CAP is "Proceeds without potentially unbounded waits."

> Paxos is another example.

Paxos isn't a magic wand, either.

You should read http://pl.atyp.us/wordpress/?p=2521.