"Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services"

The CAP theorem states that it is impossible for a internet service to simultaneously provide consistency, availability, and partition-tolerance. Only any two of the three can be provided. By consistency, Brewer meant atomic data objects, such that it appears that each operation was completed at a single instant (e.g. any read that occurs after a write returns the newest written value). Availability is defined as the guarantee that every request by a non-failing node will (eventually) result in a response. Partition tolerance means that the network can lose arbitrarily many messages sent from one node to another and still return a result.

The proof of this theorem uses an asynchronous network model, where there is no clock and nodes make decisions based on messages received. First, the authors prove that asynchronous networks cannot provide a data object that guarantees availability and atomic consistency when messages are lost, since a read could return data from a stale write (which was not updated due to lost messages). In synchronous (or partially synchronous) network models, a weaker form of consistency can be achieved using timeouts. In general, most web services have to settle for "most of the data, most of the time."

This theorem is highly relevant today and is becoming more and more important. Cloud computing and Internet services are increasingly relying on distributed systems, where networks are not entirely reliable (even more so as applications begin to span several datacenters). The work done in the paper was new (i.e. the theorem had not been proved), but I'm not sure that a formal proof was necessary for people to understand that only two of the three conditions can be possible at once. For me, the most interesting part of the paper was the realization that services need to determine what sort of failure is acceptable (e.g. which of the CAP) -- with web applications often valuing availability over consistency. These tradeoffs are fundamental decisions that application designers need to acknowledge and keep in mind.