Apologies, as usual with the CAP theorem, I made an error here. The Gilbert/Lynch paper specifically says that availability only counts for servers that actuall

Apologies, as usual with the CAP theorem, I made an error here. The Gilbert/Lynch paper specifically says that availability only counts for servers that actually receive requests, so if all the network links in the world are cut, you will still be available by this definition. So you can ignore the last two sentences of my first paragraph. That paragraph should say: First, in the "The same application with an Eventually Consistent store", you don't actually define the semantics of the system, so there is no way to say how it relates to CAP. Eventually consistent stores, like the original Dynamo, are designed to be AP systems, which is why they have things like read-repair. If all your nodes have failed, or all network links have been cut, you are available because there are no requests to which to respond. Otherwise, you can always get a response, and are therefore available, but that response may not be the "latest" response, so it may not be consistent (see Herlihy on Linearizability for the full definition here). Apologies for adding confusion here.