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

In one breath — the whole paper, compressed

Gilbert and Lynch formalize Brewer's conjecture for a read/write data object replicated across networked nodes. They define atomic consistency, availability, and partition tolerance, then prove by an indistinguishability construction that no asynchronous implementation can guarantee all three: after a write completes on one side of a partition, a read on the other side must either return without learning the write or fail to terminate. The paper then examines partially synchronous models, showing how bounded timing assumptions permit useful compromises while the partition-driven impossibility remains under the stated availability requirement.

Before this paper — the world it landed in

Eric Brewer conjectured in 2000 that distributed web services could not simultaneously provide consistency, availability, and partition resilience. This 2002 note supplies the missing formal model and proof. Its terms are deliberately narrow: consistency is atomic (linearizable) behavior of a read/write object; availability requires every request to a non-failing node eventually receive a response; and partition tolerance allows the network to lose arbitrarily many messages between components. The result is therefore an impossibility theorem under explicit assumptions, not the later slogan that every system freely 'picks two.'

The problem — what was actually breaking

Brewer's conjecture needed precise definitions before it could be proved or used to reason about systems.
A completed write on one side of a partition may be invisible to a read issued on the other side.
Availability forces every request received by a non-failing node to terminate even when communication is lost.
Atomic consistency requires operations to appear in one real-time-respecting serial order, so a later read cannot legally ignore a completed write.
In an asynchronous network, a node cannot use elapsed time to distinguish a delayed message from one that has been lost.
Adding timing bounds changes which compromises are implementable, but does not make information cross an enduring partition.

Core ideas — the contributions, and why they work

A precise three-property model

The paper defines a read/write data object and states atomic consistency, availability, and partition tolerance separately. This prevents the theorem from being stretched to every meaning of consistency or every operational meaning of availability.

The asynchronous impossibility

Assume a write completes in one network component and then a read is submitted in another component that receives no messages from the first. Availability requires the read to finish, while atomicity requires it to reflect the completed write. Since the reader cannot distinguish executions with different completed values, no response can be correct in all executions.

Indistinguishability, not performance

The contradiction is informational rather than quantitative: the reading component has the same local history in executions that require different answers. Faster machines, retries, or more replicas cannot supply the missing information.

Atomic consistency is the C

Consistency here is atomic consistency (linearizability) for the emulated object: every operation takes effect at a point between invocation and response and the order respects real time.

Availability is a liveness guarantee

Availability requires each request delivered to a non-failing node eventually to receive a response. It does not impose a latency target or require every response to contain fresh data.

Partition tolerance is a network model

The partition condition permits arbitrary message loss between groups of nodes. It is not an optional feature that an algorithm can simply decline when its deployment is exposed to such failures.

Partial synchrony enables bounded compromises

The later sections study models with timing bounds and describe conditions under which weakened guarantees can be achieved. These positive cases depend on the added assumptions; they do not refute the asynchronous impossibility.

How it works — the mechanism, concretely

The object and executions

Clients invoke reads and writes on an object implemented by distributed nodes. Correct executions must satisfy the specified safety and termination properties even when the allowed communication failures occur.

Complete a write

First, a client submits a write to a node in one component and receives its response, making the write precede a subsequent operation in real time.

Separate the components

The network then loses the messages needed to convey that completed value to a node in another component.

Invoke a remote read

A client submits a read to the uninformed component. Availability says that the non-failing recipient must eventually answer despite the missing messages.

Construct two indistinguishable runs

Choose two executions that differ only in the value of the completed write. The reading component has the same local state and received messages in both, so it must behave the same way.

Derive the contradiction

Atomic consistency demands different read results in the two executions, but indistinguishability forces the same behavior. Waiting forever would avoid a wrong result only by violating availability.

Change the timing model

The paper next introduces partial synchrony and analyzes what additional timing knowledge permits. Any achievable combination is conditional on those stronger assumptions or on weakening a property.

What the paper showed — measurements and proofs

The main result is a formal impossibility proof in the asynchronous network model, not an experimental performance claim.
The counterexample needs only a completed write, a later read, and loss of the messages that would carry the written value across the partition.
Two executions with different written values are indistinguishable to the reader, although atomic consistency requires different answers.
The proof grants the implementation arbitrary internal behavior; the contradiction follows from the three required properties rather than a particular protocol.
The availability definition is deliberately minimal—eventual response at every non-failing node—so violating it cannot be blamed on an aggressive latency bound.
The paper separately studies partially synchronous models to identify how extra timing assumptions change feasibility.

Limits and trade-offs — conceded and discovered

The theorem uses atomic consistency for a read/write object; it does not directly characterize transactions, application invariants, or every weaker consistency model.
Availability means eventual response by a non-failing node and says nothing about useful latency, error responses, or the freshness of returned data.
The proof models partitions through message loss and does not provide a taxonomy of correlated crashes, Byzantine faults, or recovery after a partition heals.
The result is qualitative: it does not choose a design point, measure outage probability, or quantify the business cost of stale data versus blocked operations.
Positive results in partially synchronous settings rely on their stated timing and failure assumptions and should not be read as implementations satisfying all three properties in the original asynchronous model.

What it became — the systems that inherited it

This paper converted Brewer's conjecture into the formal result now called CAP. Its lasting contribution is the explicit model and indistinguishability proof: under partitions, a linearizable operation may have to wait, while an operation required to respond may lack the information needed to be linearizable. Later systems expose many finer consistency and availability choices, but those engineering choices should be evaluated against the exact definitions and failure model proved here rather than the loose 'pick two' slogan.

In the paper’s words — verbatim

“It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: Availability and atomic consistency, in all fair executions (including those in which messages are lost).”

Theorem 1

“In this note, we prove Brewer's conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.”

Abstract

“When a partition occurs, it is impossible to provide both consistent data and availability.”

§3

Vocabulary — as this paper uses it

Atomic consistency: The read/write object must appear to execute each operation at one instant between invocation and response, in an order compatible with real-time precedence.
Availability: Every request received by a non-failing node must eventually result in a response, even during executions with message loss.
Partition tolerance: The implementation must continue to meet its claimed specification even when the network loses arbitrarily many messages between components.
Read/write data object: The simple replicated abstraction used for the proof: clients write values and later read a value, subject to atomic semantics.
Asynchronous network: A model with no known upper bound on message delay or relative process speed; permitted messages can be delayed or lost.
Indistinguishable executions: Executions whose local states and received messages are identical for a node, forcing that node to behave identically even when correctness requires different results.
Fair execution: An execution satisfying the model’s fairness conditions; Theorem 1 requires availability and atomic consistency across all fair executions, including message-loss executions.
Partially synchronous model: A stronger timing model in which bounds apply to some aspects of processing or communication, studied to identify feasible compromises.
Network partition: A communication failure that separates nodes into components so information produced in one component may not reach another.

On the timeline — where this sits in the story

Year2000–2002

MilestoneCAP theorem / Brewer’s conjecture formalized

Problem solvedDistributed-system designers needed a clear framework for the trade-offs caused by network partitions.

How it solved itCAP clarified that under partition, systems must trade off consistency and availability.

Why it matteredStrongly shaped NoSQL and distributed database design debates in the 2000s and 2010s.

DDIACh. 9: Distributed Systems Ch. 10: Atomic consistency & Consensus

View on the timeline