"I mean primarily the ability to face a network partition and continue providing write service to all clients transitively connected to a majority of servers."
Probably should be a little more prominent considering it's one of the first questions you'd want answered but I was a bit careless to miss it.
Clustrix, the company I work for, offers a full SQL data store with similar quorum semantics. However, it's not free.
Google Megastore allows similar consistency semantics (with its own data model) in a cross data center "cloud" fashion. It's also not free, but it would probably be suitable for some set of Heroku customers, particularly if they're already using Google App Engine.
For example, lets say you have key A with data 'foo' living on all 3 nodes of a quorum based system. You perform a write to key A with data 'bar' and one host accepts the write and two fail resulting in your client getting a failure back. Reading data back from all nodes will return 'foo'. Time goes along and read repair or some other anti-entropy process kicks in a replicates 'bar' to the other hosts. Now a read for key A returns 'bar'. In short, when a client performs a write and gets a failure back they actually have no idea if it will update the data store or not. You cannot implement compare-and-set in that type of environment.
I think they dismissed Zookeeper too quickly without trying to understand it first. The zookeeper primitives (get/set nodes and their children) seems simpler and cleaner than doozer is client protocol, AFAICT. Zookeeper should scale better (especially for readers) than typical Paxos based systems as well.
"I mean primarily the ability to face a network partition and continue providing write service to all clients transitively connected to a majority of servers. Secondarily, I mean the ability to continue providing read-only service to all clients connected to any server."
A truly available system, in the sense of CAP, allows writes, not just reads, even under partition, even for clients not connected to the "majority" nodes. This leads inevitably to the need for conflict detection and resolution, and that whole "eventually consistent" thing. What you are describing is very useful, hence the existence of things like Chubby and ZK, but is most definitely not "available", per CAP.
Folks might also be interested in the classic paper on constructing locks from low level primitives like CAS, Herlihy's 'Wait-free Synchronization" http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A01...
