"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.
"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...