Distributed data: replication, consistency and the CAP conversation

A retail site keeps its product catalogue in one datacentre and mirrors it in three more, so that a shopper in Sydney is not waiting on a server in Virginia. The mirroring works until the link between two regions fails. The catalogue keeps serving from every region, because each holds a copy. A price change made in one region does not reach the others. A shopper in Sydney then buys a jacket at yesterday's price, while a shopper in London sees the new one. Nobody designed that. The system was never asked what to do when two copies of the same fact disagreed. This fifth unit follows the replica across the network.

The vocabulary for that situation is CAP, usually recited as a choice between consistency and availability. This lecture argues that the recitation is the least useful thing CAP has to offer. The theorem is real: under a partition a service cannot be both consistent and available, and Gilbert and Lynch (2002) proved it. What the theorem does not do is design the system. The design question is which operations tolerate staleness, under which failure, and what the application does when two replicas disagree.

The theorem forbids one combination, and its terms are looser than they sound

Brewer (2000) stated the conjecture in a keynote on what makes distributed systems fragile even when they work. Two years later, Gilbert and Lynch (2002) turned it into a proof. In the asynchronous network model, no distributed web service can be simultaneously consistent, available and partition tolerant.

The proof forbids one combination of three properties under one failure assumption. It does not say that a system is available or not. It says that consistency, the property that every read sees the most recent write, cannot be guaranteed at the same time as answering every request while the network is split. Once a designer states which operations need that freshness, the theorem becomes a constraint on one feature at a time.

Brewer (2012) returned to the idea he had proposed and argued that CAP is often misread. By handling partitions explicitly, he writes, designers can optimise both consistency and availability and obtain a trade-off across all three. He locates the design work in the two modes a system occupies: normal operation, and how it behaves while the network is split.

Fox and Brewer (1999) sharpen what available means by proposing that availability be improved through graceful degradation, characterised as harvest and yield, and mapped onto mechanisms that improve fault isolation. Harvest is the fraction of the data a system can still produce; yield is the fraction of requests it can still answer. A system that answers most requests with slightly stale data is more available than one that answers every request correctly or none at all.

Latency forces the same choice with no partition at all

Abadi (2012) argues that CAP's influence on distributed database design is more limited than its reputation suggests, and that a second trade-off, between consistency and latency, has shaped several well-known systems more directly. He proposes PACELC to record both cases. With a partition, trade availability against consistency. Without one, trade latency against consistency. Reading from a replica on another continent is slow even when nothing is broken, so freshness is a question asked on ordinary requests, and on a metered mobile connection the bytes are an ordinary cost too.

Abadi (2012) classifies the default configurations of Dynamo, Cassandra and Riak as giving up consistency under partition and, in normal operation, giving it up again for lower latency. Fully ACID systems such as VoltDB refuse both trades and pay in availability and latency instead. He places PNUTS and MongoDB in the two less common cells. The classification is per configuration rather than per product, which is this unit's claim in miniature: the label belongs to the setting, not to the brand.

Dynamo shows what availability cost Amazon, and who paid

The clearest worked case is Dynamo. DeCandia and colleagues (2007) describe the highly available key-value store beneath several Amazon services. It exposes an interface addressable by primary key only, replicates data with consistent hashing, and resolves conflicting versions through object versioning and application-assisted reconciliation, giving up consistency under some failure scenarios. A shopping cart is the canonical instance. The price is that two carts for the same customer can coexist, and the application must decide how to merge them.

The workload is reported rather than asserted. DeCandia and colleagues name the services for which they judge a relational store would limit scale, among them the shopping cart, session state, customer preferences, best-seller lists and sales rank. They record that the shopping cart service served tens of millions of requests producing well over three million checkouts in a single day. A customer should be able to view and add to a cart even while disks fail, network routes flap, or a datacentre is destroyed. Availability there was not a desirable property but the reason the service was built as it was.

Terry and colleagues (1995) described Bayou, a weakly connected replicated store in which update conflicts are managed by application-supplied merge procedures and dependency checks. Bayou made application-assisted reconciliation concrete more than a decade before Dynamo, and fixed the bargain: the storage layer keeps serving while the application supplies the rule for what happens when two writes meet.

The family consolidates, and one system refuses the trade

Lakshman and Malik (2010) describe Cassandra, a decentralised structured storage system that runs across commodity servers with no single point of failure. It combines a distribution in the Dynamo style with a data model in the Bigtable style, and it continues to serve as components fail.

The strongest counter-example to the popular reading is Spanner. Corbett and colleagues (2012) describe Google's globally distributed database, which provides externally consistent reads and writes and globally consistent snapshots across datacentres while remaining available, using TrueTime to bound clock uncertainty. Spanner does not refute the theorem. It pays for the guarantee in latency and in a physical dependency, because TrueTime is built on atomic clocks and GPS receivers. Dropping consistency or availability is therefore a false economy at that scale.

Relaxed consistency is buildable, and the application still pays for it

Lloyd and colleagues (2011) identify causal consistency with convergent conflict handling, called causal+, as the strongest consistency achieved under the latency and availability constraints of geo-replicated stores. They build the COPS system to provide it. Eventual consistency is not the only option for a store that must answer quickly around the world.

Shapiro and colleagues (2011) supply the other constructive answer. They define conflict-free replicated data types, whose replicas merge automatically because their operations converge, giving eventual consistency without application-level reconciliation. The obligation Dynamo exposed can be discharged in the data type instead, by choosing a structure whose concurrent writes cannot conflict.

Not every obligation can be discharged that way. Vogels (2009) gives the industry framing: eventual consistency is one of the models open to a developer building at worldwide scale, a trade-off rather than a defect. Bailis and Ghodsi (2013) supply the harder question. They review eventual consistency, its limitations and the extensions proposed since the conjecture, and ask how an application can be built on eventually consistent infrastructure when the guarantee is not one of safety. If the store will not prevent a stale read, the application has to tolerate one.

Contested question: does CAP constrain the design, or distract from it?

The literature disagrees about what CAP is for, not about whether the proof holds.

One position holds that the theorem is the design constraint. A system claiming all three properties under a partition is either not consistent in the sense the proof uses, or not available, or not partition tolerant. The value of CAP, on this view, is that it rules out a wishful design, and every question about staleness is good engineering inside that boundary. Gilbert and Lynch (2002) supply the formal result; the popular reading Brewer later corrected states it crudely.

The opposing position holds that CAP describes too little to govern a choice, and that the binding constraints lie elsewhere. Abadi (2012) locates the more influential trade in latency. Brewer (2012) argues that handling partitions explicitly lets a designer optimise both consistency and availability, and Bailis and Ghodsi (2013) put the real decision in the application, which must tolerate the staleness it is given. Spanner (Corbett et al., 2012) strains this position hardest, keeping strong consistency and availability at global scale.

One reads it as a boundary on what can be built, the other as a first lesson pointing to the constraint that actually binds. What would settle it is not another proof but a measurement the literature has not attempted. Place one application on a strongly consistent store and on an eventually consistent one. Record, for each operation, the staleness window, the latency and the availability delivered during a region failure. Spanner reports such figures for one company and COPS for one research system. Ferreira and colleagues (2024) come part of the way, deploying three NoSQL stores across single- and multi-region clouds and measuring throughput and response time as the consistency setting changes, but the same application has still not been priced across both families.

Rate each side by its evidence. Gilbert and Lynch (2002) prove a theorem inside one failure model, the strongest formal result here. Abadi (2012) argues a position, Brewer (2012) reflects on the conjecture he proposed, and Bailis and Ghodsi (2013) survey the field, so the distraction side rests on argument rather than measurement. Corbett and colleagues (2012) report one system, a case rather than a comparison. The strongest objection is that the theorem still rules out whole designs, so a designer who reasons feature by feature can propose a system the proof forbids. While the dispute is open, a designer states, for each operation, how stale an answer may be and what happens when replicas disagree.

Where the argument is heading

The direction of travel is towards stating the guarantee one operation at a time. Lloyd and colleagues (2011) name the strongest model available under geo-replication. Shapiro and colleagues (2011) move the reconciliation obligation into the data type. Spanner (Corbett et al., 2012) publishes both the guarantee and the physical cost of its clock infrastructure. Kleppmann (2017) draws the trade-offs together at book length for readers who must choose rather than recite. A system should say, for each operation, how stale an answer it will accept and what it does when two replicas disagree.

The sources this unit rests on

• Brewer, E. A. (2000). Brewer's keynote surveys what makes distributed systems fragile even when they work, covering fault models, availability, graceful degradation and data consistency, and states the conjecture later called CAP.
• Gilbert, S. and Lynch, N. (2002). The authors prove that no distributed web service can be simultaneously consistent, available and partition tolerant in the asynchronous network model, then discuss how the dilemma is met in the partially synchronous model.
• Brewer, E. (2012). Brewer argues that CAP is often misread, and that handling partitions explicitly lets designers optimise both consistency and availability and obtain a trade-off across all three.
• Abadi, D. (2012). Abadi argues that CAP's impact on modern distributed database design is more limited than often perceived, and that a consistency-versus-latency trade-off has influenced several known systems more directly; he proposes PACELC to unify the two cases.
• Bailis, P. and Ghodsi, A. (2013). The authors review eventual consistency, its limitations and the extensions proposed since the conjecture, and ask how applications can be built on eventually consistent infrastructure given no guarantee of safety.
• Vogels, W. (2009). Vogels presents eventual consistency as one of the models open to a developer building at worldwide scale, framing the choice as a trade-off rather than a defect.
• DeCandia, G., Hastorun, D., Jampani, M. et al. (2007). The authors describe Dynamo, the highly available key-value store beneath several Amazon services, which exposes a primary-key-only interface, replicates with consistent hashing, and resolves conflicts through object versioning and application-assisted reconciliation.
• Lakshman, A. and Malik, P. (2010). The authors describe Cassandra, a decentralised structured storage system running across commodity servers with no single point of failure, combining a Dynamo-style distribution with a Bigtable-style data model. It shows the design conversation consolidating into a family with stated consistency options.
• Corbett, J. C. et al. (2012). The authors describe Spanner, Google's globally distributed database, which provides externally consistent reads and writes and globally consistent snapshots across datacentres while remaining available, using TrueTime to bound clock uncertainty. It is the strongest counter-example to this unit's thesis, strong consistency being kept at global scale at a cost in latency and clock hardware.
• Shapiro, M., Preguica, N., Baquero, C. et al. (2011). The authors define conflict-free replicated data types, whose replicas merge automatically because their operations converge, giving eventual consistency without application-level reconciliation.
• Ferreira, S., Mendonca, J., Nogueira, B. et al. (2024). Deploys MongoDB, Redis and Cassandra across single- and multi-region cloud deployments and measures throughput and response time as the consistency setting changes, reporting where strong consistency costs most for each store. It prices the staleness trade the unit's theory describes. It measures one store family, not a cross-family comparison.
• Fox, A. and Brewer, E. (1999). The authors propose improving availability through graceful degradation, characterised as harvest and yield, and map that degradation onto mechanisms that improve fault isolation. The registrar dates the proceedings to 2003, although the identifier places the paper in the 1999 HotOS workshop.
• Terry, D. B., Theimer, M. M., Petersen, K. et al. (1995). The authors describe Bayou, a weakly connected replicated storage system in which update conflicts are managed by application-supplied merge procedures and dependency checks. It is the origin of the merge-procedure approach, and places the reconciliation obligation on the application by design.
• Lloyd, W., Freedman, M. J., Kaminsky, M. et al. (2011). The authors identify causal consistency with convergent conflict handling, called causal+, as the strongest consistency achieved under the latency and availability constraints of geo-replicated stores, and build the COPS system to provide it.
• Kleppmann, M. (2017). Kleppmann's book compares the storage and processing models available for data-intensive applications, written to weigh trade-offs rather than recommend a product. Only the publisher metadata and the book's website were verified, because the chapters sit behind a subscription.