When I’m talking to people about Eric Brewer’s CAP Theorem, one of the things that’s hardest to explain is the operative definitions of availability and partition tolerance. An “intuitive definition” is no definition at all, and a definition borrowed from another context might be even more misleading. I saw an example of this on a mailing list just last night. A genuine cluster expert was using definitions that were relevant for a particular kind of clustering fifteen years ago to cast aspersions on the relevance or import of more recent work on different kinds of systems. His definitions were clearly the wrong ones, and his immature comments about Lynch as a guy from Berkeley (even though she’s at MIT) weren’t exactly endearing either. I guess I should thank him for inspiring this post, though.

The first thing we need to get out of the way is that the actual words “availability” and “partition tolerance” are either meaningless or misleading here. Call them A and P instead. Both A and P have to do with availability. Both A and P have to do with partitions. Got it? The choice was made to use “availability” for one property that a system might have and “partition tolerance” for the other, but if the labels had been swapped they’d make about as much sense. You have to look at the context (for Brewer) or the formal definition (for Lynch) – not just the words.

It’s actually easiest to work backwards a little bit, starting with Nancy Lynch’s more formal 2002 SIGACT paper. Here’s how that paper defines availability and partition tolerance.

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response.

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.

Lynch also makes the point that unbounded delay is indistinguishable from failure. Time is therefore an essential component of these definitions (a point made even more explicitly in the Dynamo paper). What they leave unclear is the precise dividing line between node and network failure, and therefore between availability and partition-tolerance problems. For that, we go back in time to Brewer’s 2000 PODC keynote. Brewer doesn’t actually provide very clear definitions, but he does leave a very important clue in slide 16.

Forfeit Availability

Make minority partitions unavailable

What he’s talking about here is quorum, and this is where a lot of confusion comes from. Somebody from a high-availability clustering background, such as myself or the aforementioned expert, is likely to think of quorum requirements as a way of maintaining availability. We would have interpreted Lynch’s definitions in that light, and yet here Brewer explicitly presents quorum requirements as forfeiting availability. What’s going on? Well, remember what I said about the words being meaningless? The key to resolving this apparent contradiction is to stop thinking about the words, and start thinking in terms of nodes, requests, and bounded time.

  • Availability is sacrificed if certain nodes are forced to wait for unbounded time because of a failure. This includes the common approach of forcing non-quorum nodes down, which Brewer alludes to.
  • Partition tolerance is sacrificed if certain requests are forced to wait for unbounded time because of a failure. This is most often the case when a node holding a lock cannot be reached, and quorum loss is not used to break the lock.

This brings us (finally) to the practical implications for different types of systems. Let’s consider the case of a single resource and three nodes interested in that resource when a partition occurs, according to the following diagram.

What are the practical implications for different CAP systems if Y and Z receive requests for the resource?

  • In an available but not partition-tolerant system, Y would be allowed to process its request because it can reach X to obtain the lock. Z’s request would be blocked because X is unreachable.
  • In a partition-tolerant but not available system, Z would be allowed to process its request because it is part of the quorum group (X’s lock will be broken). Y’s request would be blocked because it is not part of the quorum group.
  • In a system that is both available and partition-tolerant, both requests would be allowed to progress. Y would return current data as possibly modified by X, while Z would return possibly stale data. Consistency is obviously sacrificed in this case. Note that maintaining consistency is possible in the other two kinds of systems (which is not to say that it’s easy).

I hope this clarifies what availability and partition tolerance actually mean in a CAP context, and more importantly what the implications are for systems that have to deal with these tradeoffs.