The previous lesson ended with a table in which Kilometre Zero assigned a different consistency model to each piece of data: linearizability for the last unit of aged-cheese, session guarantees for Anna's basket, eventual consistency for the visit counter. The obvious question was left hanging: if linearizability is the most comfortable guarantee for the programmer, why not give it to everything? The answer is that it has a price that is not paid in euros but in availability when the network fails and in latency when it does not, and that price is formalised in two results: the CAP theorem and its extension, PACELC.

Few results in computer science are quoted as often and understood as poorly as CAP. This lesson states it with the precision with which Gilbert and Lynch proved it, explains why the "P" is not an option you can discard and why the real choice is what to sacrifice during a partition, and takes apart the most widespread misunderstandings ("pick two out of three", "AP means no consistency"). We will then introduce PACELC, which adds what CAP is missing (the trade-off between latency and consistency when everything works), and use it to classify the systems that will appear in the rest of the course. We will apply both to Kilometre Zero's data with a table of justified decisions, and a Python simulation will show the same pair of replicas, inv-bcn/inv-vlc, behaving in CP mode (rejecting writes without a quorum) and in AP mode (accepting, diverging and losing a reservation on reconciliation). We will finish with the modern criticisms of the theorem, which do not invalidate it but do force us to use it with more care. The specific mechanisms by which a CP system reaches agreement (consensus), and read and write quorums, are the next two lessons.

1. The precise statement of CAP
2. Why partitions are not optional
3. The real choice: CP or AP during a partition
4. Common misunderstandings
5. PACELC: what happens when there is no partition
6. Table of classified systems
7. Deciding per use case at Kilometre Zero
8. Simulation: the same system in CP mode and in AP mode
9. Criticisms and nuances: harvest, yield and "please stop calling databases CP or AP"
10. Common mistakes and tips
11. Exercises
12. Conclusion

Eric Brewer presented CAP as a conjecture in a talk in 2000; Seth Gilbert and Nancy Lynch proved it formally in 2002. The proof is simple, but only if the three letters are properly defined, and this is where the confusion starts, because in everyday usage each one means something vaguer than what the theorem says:

With those definitions, the theorem says: in an asynchronous distributed system in which partitions can occur, it is impossible to guarantee linearizability and availability at the same time.

The proof fits in one paragraph. Take a register with initial value v0 replicated on two nodes, N1 and N2, and a partition that separates them. A client writes v1 to N1. By availability, N1 must answer "done" without waiting for N2 (which it cannot talk to). Another client then reads from N2. By availability, N2 must answer; but N2 has received nothing from N1, so it can only answer v0. That history (a completed write of v1, a later read that returns v0) is exactly history 1 from 03-01: it is not linearizable. So either N1 does not answer (sacrificing A), or N2 returns a stale value (sacrificing C). There is no third option.

A naive reading of the theorem ("pick two of C, A and P") suggests that you can give up P and keep C and A. In a real distributed system that option does not exist, for two reasons we already know from Module 1:

• The network is unreliable (fallacy 1 of 01-04). Severed cables, switches that reboot, badly applied routing tables, a firewall that drops packets, a node so overloaded that it does not answer in time (remember that in an asynchronous system, 01-02, "slow" and "partitioned" are indistinguishable). The question is not whether there will be partitions but how many times a year.
• Giving up P means that, when a partition happens, the system stops honouring C, A or both in an uncontrolled way. In other words, "CA" is not a design choice but the absence of one: the system will behave somehow during the partition, and if the designer has not decided how, it will be the worst way.

The only thing you can do is reduce the likelihood and the scope of partitions: nodes in the same rack, redundant networks, or simply a single node. A PostgreSQL database on a single machine is "CA" in the trivial sense that there is nothing to partition, which is why the Kilometre Zero monolith of 01-06 never had to think about this. As soon as inventory has inv-bcn in Barcelona and inv-vlc in Valencia, joined by 350 km of fibre it does not control, P is settled.

With P fixed, the theorem boils down to one decision: when the partition happens, what does a node that cannot talk to the others do?

• CP (consistency over availability): the node that cannot coordinate rejects the operation (or blocks it until the partition heals). In the diagram, N1 would answer Anna "I cannot confirm the reservation right now", and N2 would answer Mark "I cannot guarantee you a current value". Nobody reads stale data, but part of the system, or all of it, stops serving. In practice, a CP system usually keeps the side of the partition that has a majority (quorum) running and shuts down the minority side; how it is decided who has the majority is the consensus of 03-03.
• AP (availability over consistency): both nodes keep answering with what they have. Anna reserves on N1, Mark reads (and perhaps reserves) on N2, each side accumulates writes the other cannot see, and when the partition heals you have to reconcile: decide what happens with two reservations of the same last cheese. Reconciliation can be as simple as "the last one wins" (with data loss) or as sophisticated as a CRDT from 03-01 (no loss, but no invariants).

Notice that the choice is neither global nor permanent: it is per operation and during the partition. A system can be CP for writes and AP for reads; it can be CP for stock and AP for the basket; and outside a partition, both letters are honoured with no conflict. A well-designed system behaves identically 99.9% of the time whether it is CP or AP; the label only describes what it does in the remaining 0.1%.

Daniel Abadi observed in 2012 that CAP ignores the system's normal state. Most of the time there is no partition at all, and yet systems keep making trade-offs: every linearizable write has to coordinate with other replicas before answering, and that coordination costs one or more network round trips. PACELC puts it like this:

If there is a Partition, choose between Availability and Consistency; Else (when there is none), choose between Latency and Consistency.

The second half is the one that describes day-to-day life. With inv-bcn and inv-vlc connected and healthy, a linearizable reservation (EC) requires inv-bcn to wait for confirmation from inv-vlc before telling Anna "done": about 10 ms for the Barcelona-Valencia round trip, more at the 99th percentile. A reservation in EL mode answers as soon as it is written locally and replicates in the background; Anna sees a response in 1 ms, in exchange for inv-vlc possibly being a few milliseconds behind (the delayed propagation of the simulation in 03-01). The four resulting combinations:

PACELC is not a theorem but a classification framework, yet it turns the abstract discussion into a concrete question you can put to any store: "what do you do during a partition, and how many network round trips do you make per write when there is none?".

The systems that will appear in the rest of the course, classified with PACELC. Many are configurable, which is why the classification states the configuration:

Two remarks on the table. First: the same database appears in different rows, because the choice is made per configuration and often per operation; this is what Kleppmann criticises in section 9. Second: coordination systems (etcd, ZooKeeper) are always PC/EC and gladly accept the cost, because their job is precisely to be the source of truth on who the leader is or what the current configuration is; an AP coordination system would be useless.

With the framework in hand, let us go back to the table in 03-01 and justify each choice by thinking about what happens during a partition between Barcelona and Valencia (or between the cloud where the services live and the producers' physical shops) and about the acceptable latency the rest of the time:

The rule that emerges: CP for what is irreversible or contended (money, the last unit, leadership); AP for what can be corrected, merged or simply ignored (baskets, positions, counters, catalogue). And the pink-tomato row shows that the decision can depend on the state of the data, not just on its type.

We are going to build two inventory replicas that can operate in either mode, and a network that can be partitioned. In CP mode, a reservation is only confirmed if both replicas accept it (with two nodes, the "quorum" is unanimity; in 03-04 we will see majority quorums with N=3). In AP mode, each replica accepts locally and records the timestamp; when the partition heals, reconciliation is done with last-write-wins.

Output:

What is happening, step by step:

• CP mode: during the partition, reserve checks whether it can reach the other replica before touching anything. It cannot, and it raises NoQuorum: neither Anna nor Mark can reserve. The system has sacrificed availability (two live nodes answering with an error) and preserved linearizability: no anomalous history is possible because there have been no writes. When the partition heals there is nothing to reconcile. With N=2, this mode is fragile: any partition shuts the whole system down. With N=3 and a majority quorum (03-03 and 03-04), the side with two nodes would keep taking reservations.
• AP mode: each replica accepts its customer's reservation and deducts from its local copy. Both answer, both end up at zero, and both believe they have sold the last cheese: the read "0 / 0" looks coherent but hides two reservations. On reconciling with LWW, the system compares stamps, keeps the write from inv-vlc (stamp 2) and discards the one from inv-bcn. The final stock (0) is wrong (it should be -1, which means one of the two customers will not get their cheese) and, worse, Anna's reservation has vanished from the stock state even though it is still in the reservation list of inv-bcn. Nobody will find out until Montblanc Dairy receives two orders for one unit.

The experiment shows both faces of the theorem in stark terms: CP protects the invariant at the price of turning customers away; AP keeps every customer happy during the partition and breaks the invariant for them afterwards. It also shows that LWW is the worst possible reconciliation for contended data: it silently discards an entire write. An operation-based reconciliation (adding up the deductions from both sides: 1 - 1 - 1 = -1, detecting the negative and compensating Mark's order) or a threshold that switches to CP mode when few units are left, as the table in section 7 suggested, would be the alternatives; conflict resolution strategies are covered in 03-04, and the compensation of Mark's order in 03-05.

CAP is correct as a theorem, but its use as a label for systems has drawn serious criticism that is worth knowing:

• It is too narrow. It only covers one consistency model (linearizability), one kind of failure (partition) and a very particular notion of availability. It says nothing about latency (which is why Abadi proposed PACELC), about node failures that are not partitions, about transactions or about data partitioning. A system can be impeccably "CP" and still lose data to a corrupt disk, or be "AP" and be down because of a deployment error.
• Kleppmann (2015), "Please stop calling databases CP or AP". Martin Kleppmann argues that the definitions in CAP are so specific that almost no real system fits cleanly: MongoDB is not "CP" because reads from secondaries are not linearizable and w:1 writes do not survive a failover; Cassandra is not "AP" in the formal sense when used with a quorum; and "available" in the Gilbert-Lynch sense (every live node responds) is a property almost nobody wants literally (is an isolated node that answers with hour-old data "available" in any useful sense?). His proposal: describe systems by the specific guarantees they offer (the vocabulary of 03-01) and by their behaviour under specific failures, rather than by a letter. The table in section 6 was built in that spirit: each row states the configuration and the behaviour, not just the label.
• Brewer (2012), "CAP twelve years later". Brewer himself clarified that "two out of three" is misleading, that the choice is per operation and during the partition, and that the interesting part is designing the handling of the partition: detecting it, entering an explicit partition mode (limiting operations, logging what is done), and, once it heals, recovering (reconciling, compensating). The AP-mode simulation in section 8 lacks precisely that third phase done properly.
• Harvest and yield (Fox and Brewer, 1999). A finer way of thinking about availability. Yield is the fraction of requests that get answered; harvest is the fraction of the data reflected in the answer. A search engine whose index is split into 10 shards and loses one can answer 100% of queries (yield 1) with 90% of the data (harvest 0.9). Applied to Kilometre Zero: during a partition, a market's page can show the reachable producers and leave out the rest with a notice, instead of failing altogether. It is a form of graceful degradation that CAP, with its binary A, has no way of describing.

The lesson from these criticisms is not to abandon CAP but to use it for what it is: a formal reminder that coordination has a price and that the price must be decided per piece of data and per operation, with the precise vocabulary of 03-01 and not with two letters.

• Presenting a system as "CA". If somebody says it of a system with more than one node, either they have not thought about partitions or they are describing a single server. Ask what each node does when it cannot talk to the others.
• Labelling the whole platform with one letter. Kilometre Zero is neither CP nor AP; the stock of the last unit is CP and the basket is AP. The decision is per piece of data and per operation, and sometimes per state of the data.
• Choosing AP and reconciling with LWW without looking at what gets lost. LWW is the default strategy of many stores (Cassandra among them) and is correct for data where the last write really is the right one (a courier's position, a user profile edited by a single person). For data that accumulates or is contended, it discards entire writes. Check with a simulation like the one in section 8 before accepting the default configuration.
• Confusing a slow node with a partition... or not confusing them. In an asynchronous system there is no observable difference. A CP system will treat a very slow node as isolated and stop counting on it; that is correct, but it means that timeouts (02-03, 07-04) are part of the CAP decision, and timeouts that are too short turn congestion into frequent partitions.
• Forgetting the E of PACELC. The cost of consistency is paid every day in latency, not just during partitions. If the linearizable reservation of aged-cheese requires Barcelona-Valencia coordination, the 99th percentile of ReserveStock will reflect it. Measure before deciding (07-01).
• Tip: explicitly design Brewer's three phases for every piece of AP data: how the partition is detected, which operations are allowed while it lasts and how reconciliation is done afterwards. If you cannot describe the third phase, that data should be CP.
• Tip: when somebody asks you "is this CP or AP?", answer with the specific guarantees: "reservations are linearizable via a quorum and are rejected if there is no majority; catalogue reads are eventually consistent with a typical lag of 200 ms".

For each of the following pieces of Kilometre Zero data, decide CP or AP during a partition, state the L or C choice in the absence of a partition and justify it in two sentences. Then state which reconciliation strategy you would use for the AP ones.

1. Lucy's wish list (products marked for later).
2. The number of active reservations of a courier (which limits how many more orders can be assigned to them; maximum 8).
3. The average rating (1-5 stars) of Roble Alto Winery.
4. The status of an order (created → paid → out_for_delivery → delivered).

Modify Inventory so that the mode is decided per product and per state: if the product's stock on the local replica is above a threshold (say 5), the reservation is processed in AP mode; if it is less than or equal to it, in CP mode. Load pink-tomato with 20 units and aged-cheese with 1, partition the network and have Anna and Mark reserve both products from different replicas. Show the output and explain what has been gained compared with the two pure modes.

Replace reconcile_lww with reconcile_by_operations, which instead of choosing one write computes the real stock as initial_stock - reservations_on_bcn - reservations_on_vlc and, if the result is negative, returns the list of reservations that must be compensated (the last ones accepted, by timestamp). Run the AP scenario with 1 unit and with 2 units and comment on the difference from LWW. What information does this reconciliation need that LWW did not?

Solution 1:

1. Wish list: AP / EL. An unavailable wish list is a nuisance with no cost, and an item that appears twice is trivial to fix. Reconciliation by union (OR-Set, a set CRDT: an "add" is never lost; a "remove" only deletes the "adds" it had seen).
2. Active reservations of a courier: CP / EC. The limit of 8 is an invariant of the "do not deduct below zero" kind: if both sides of the partition assign orders to the same courier, they may end up with 10. Since this is an assignment decision (not one facing the end customer), a temporary rejection is acceptable: the order stays "pending assignment" as in case 5 of exercise 3 in 02-05.
3. Average rating: AP / EL. It is a statistical aggregate; a tenth of a star of difference between replicas for a few seconds is irrelevant. Reconciliation with two GCounters (sum of scores and number of votes), which converge without loss.
4. Order status: CP / EC for the transitions, though with a caveat. The status advances through a state machine with irreversible transitions (a delivered order does not go back to "paid") and each transition is performed by a single service (payments marks it paid, delivery marks it delivered), so real conflict is rare; but two sides accepting different transitions (cancelled on one, out_for_delivery on the other) would create a meaningless state. Writes must go to the leader of km0_orders with a quorum; reads of "my orders" can be AP with session guarantees.

Solution 2:

(Renaming the original reserve to _reserve_with_mode.) With pink-tomato at 20 units, both reservations during the partition are accepted in AP mode and, on reconciling by operations, the stock ends up at 18 with no overselling; with aged-cheese at 1, both are rejected in CP mode. We have gained availability for the 99% of products (those with stock to spare) while keeping the invariant protected only when it matters. The cost: the decision is taken using the local stock, which during the partition may be higher than the real one (the other side has deducted without our knowing), so the threshold must be greater than the number of plausible reservations during the longest expected partition. It is an example of what Brewer calls "managing the partition" instead of enduring it.

Solution 3:

First, reserve must keep the stamp of every accepted reservation (the stock only stores the last write, so the history has to be recorded separately). Change the field in Replica to reservations: list[tuple[int, str, str]] (stamp, customer, product) and the two append calls to local.reservations.append((self.clock, customer, product)) (and, in scenario, the comprehension that lists the reservations becomes for _, c, _ in r.reservations). Then:

With 1 unit: real stock=-1; to compensate: [('Mark', 'inv-vlc')]. Anna's reservation (stamp 1) is kept, the stock ends up at 0 and orders is instructed to cancel Mark's order (the compensation of a saga, 03-05). With 2 units: real stock=0; to compensate: []. Compared with LWW, which left the stock at 0 "by chance" and lost a reservation without anybody knowing, this reconciliation produces a correct state and an explicit list of damage to repair. What it needs, and LWW does not, is the history of operations on each side (not just the last value) and a business rule to decide whom to compensate. It is the difference between replicating states and replicating operations, which will come up again in 03-04.

The CAP theorem, stated precisely, says that a distributed system cannot guarantee both linearizability and that every live node responds while the network is partitioned; and since partitions are not optional as soon as there are two nodes and a cable, the real choice is what to sacrifice during the partition: CP rejects the operations it cannot coordinate, AP accepts them and reconciles later. We have taken apart the usual misunderstandings (you do not "pick two out of three"; AP is not "no consistency" but no linearizability, and it allows causal and session guarantees; CP does not mean a total outage), and we have added PACELC to describe the daily cost of consistency in latency when there is no partition, with a table that classifies PostgreSQL, Cassandra, DynamoDB, MongoDB, Spanner and etcd by configuration. Applied to Kilometre Zero, the criterion has been clear: CP for what is irreversible or contended (payments, the last unit, leadership), AP for what can be merged, corrected or ignored (basket, positions, counters, catalogue), with the subtlety that the same data may switch mode depending on its state. The simulation made both faces visible: CP mode turned Anna and Mark away during the partition, and AP mode accepted them both and silently lost a reservation when reconciling with last-write-wins. Kleppmann's criticisms and the concepts of harvest and yield remind us that the two letters are a starting point, not a description, and that what needs documenting are the specific guarantees and the three phases of partition handling.

We have said several times that a CP system "rejects writes without a quorum" and that "the side with the majority keeps working", as though it were obvious how a group of nodes, with messages getting lost and no global clock, decides which side is the majority, who is in charge and which value is final. It is not obvious at all: it is one of the hardest problems in distributed computing, solved by algorithms with names of their own that Kilometre Zero will need, among other things, so that only one instance of the outbox relay from 02-05 is publishing at any given moment. That problem is consensus, and Paxos and Raft are the subject of the next lesson.