Once data lives in several copies, what may a reader see, and what must we give up when the network splits?
Replication buys reliability, performance and scale, but copies drift, and keeping them identical needs the global synchronisation replication was meant to avoid. The way out is to relax consistency and write the relaxation down as a contract. Data-centric models state what all processes may observe (bounded deviation, sequential, causal); eventual consistency only promises convergence; client-centric models promise a single mobile client that its own view never goes backwards. The hard limit is the CAP theorem: during a network partition, a replicated service cannot answer every request and stay atomically consistent; without a partition it can do both. Most large services choose availability and live with BASE.
M3 borrows heavily from Tanenbaum & van Steen [2017]. Replication keeps several copies of the same data on different machines, for three reasons:
But keeping replicas up to date consumes bandwidth: is there a benefit overall? At first glance the benefits look unquestionable:
So should we just replicate data, processes, whatever, and be content with it? No: replication has its own problems.
Web caching. Browsers cache fetched pages, so a page requested again appears instantly. But if the page changed on the server, the user gets a stale copy. Preventing that hurts either way:
Access versus update rate. A process P reads a local replica N times per second; the replica is updated M times per second, each update fully refreshing it. If N ≪ M, most versions shipped are never read, and their network traffic is wasted. Is the local replica worth it, or should updates propagate differently?
Scalability problems usually show up as performance problems, and replication and caching are the standard cure. But keeping copies consistent can itself become a scalability problem. Intuitively, copies are consistent when they are always the same, so a read at any copy returns the same result. Then an update must reach all copies before any subsequent operation: synchronous replication, whose result is informally called tight consistency.
The key idea is to update all copies as one atomic operation, or transaction. That is hard when operations must also be fast: replicas must first agree on when exactly each update is applied, e.g. on a global order of operations (Ch. 2's bank replicas). Global synchronisation takes a lot of communication, and the slides ask whether we are “bumping into another set of impossibility theorems”. We are: CAP (§6) and FLP (Ch. 6).
Is the cure worse than the disease? There is no general answer, but often a solution: relax the consistency constraints. Drop atomic updates, avoid instantaneous global synchronisation, gain performance, and accept that replicas are not always the same. When and how far that is acceptable depends on the access and update patterns of the data and on the purpose of its use.
Instead of one notion of consistency we can define several, each fitting different scenarios, so that engineers can trade the costs of consistency against its benefits. Each consistency model can then be implemented by different protocols, whose features affect how well it works.
Historically, the first things to be distributed are data. So the first problem is consistency of data across copies, and the actions to account for are operations over data. The setting is a data store: logically one store, physically distributed and replicated across processes, each working on a local or nearby copy.
A consistency model is essentially a contract among the processes and the data store, ensuring the correctness of data given a set of rules that processes have to follow.
What is “correct” depends on what processes expect, which is hard to define without a global notion of time (Ch. 2). The definition shifts the focus from the replicated data to the processes using it and their application needs. Different needs, different contracts, in two families: data-centric models constrain what all processes observe; client-centric models what one client observes.
The first contract does not demand equal copies; it imposes limits on the deviation between replicas. The level of consistency is set along three independent axes:
These bounds define continuous consistency. Deviation is measured on a unit of consistency, the conit. A data store's nature suggests its conit, but the model (and replication) is defined around a suitably designed one, and deviation is measured as differences of conits. There is no absolute measure: choose the conit for the resource and problem at hand. Granularity matters (Fig. 5.2).
The next models come from parallel and concurrent environments, where processes access shared resources simultaneously. To commit to a state for the replicas, processes must agree on a global ordering of updates.
Main idea: all update operations are seen by all processes in the same order. A data store is sequentially consistent when the result of any execution is the same as if
Any interleaving will do, if one exists and everybody sees it; real time plays no role. Take two processes, with x = y = 0 initially:
P1: W(x)1; R(y)? · P2: W(y)1; R(x)?Can both reads return 0? R(y) must then precede W(y)1, and R(x) precede W(x)1. With program order that is a cycle: W(x)1 → R(y) → W(y)1 → R(x) → W(x)1. No sequential order exists, so sequential consistency forbids both reads returning 0; every other combination is allowed. This “store buffer” history is Instrument 1's first preset.
A data store is causally consistent when all processes see write operations that are in a cause/effect relation in the same order.
It weakens sequential consistency: ordering is limited to operations in a cause/effect relation, and concurrent writes may be seen in different orders by different processes. The relation is happens-before (Ch. 2) on operations: program order, plus a read follows the write whose value it returns (write as send, read as receive). Every sequentially consistent history is causally consistent, since its single order respects causality. Not conversely: the store-buffer history is causally consistent, because its two writes are concurrent.
The slides introduce the weakest model at the start of the client-centric part, as the scenario that motivates it: a large distributed data store with almost no update conflicts. Typically a single authority updates and many processes read, so the only conflict is read-write: one process updates an item while another reads it (DNS changes, Web content). Readers may get non-updated data, which is mostly acceptable. If no update takes place for a while, all replicas gradually become consistent: eventual consistency. It promises convergence, so it allows any finite history whose reads return already-written values, provided replicas agree once updates stop.
Pick a history (all variables start at 0) or type your own, one line per process, e.g. W(x)1 R(y)0. The checker searches for a sequential order, for causally consistent per-process views, and for values nobody wrote.
Switch perspective to data sharing in mobile computing. A client connects to different replicas over time, and their differences should be transparent (Ch. 1). Simultaneous updates are not the issue. An eventually consistent store works while a client always talks to the same replica; when it moves, the new replica may lack what the client saw, or wrote, a minute ago.
Client-centric consistency models ensure that whenever a client connects to a new replica, that replica is up to date according to the client's previous accesses to the same data at other replicas. Consistency no longer refers to the resource itself (its nature, its dynamics) but to the view each client has of it.
Four client-centric models [M3]
The guarantees are per client and independent. Each covers one pair of operations by the same client at two replicas (Instrument 2).
A client does one operation at replica L1, moves, and does a second one at L2. Choose the two operations and whether L1's updates have reached L2 in between.
Supporting replication means deciding where, when and by whom replicas are placed, and which mechanisms keep them consistent. Replica management has two subproblems, and they are not the same problem:
Replication is not merely of data. Service replication replicates functions, for the same reasons, which may or may not rely on the same data store: two layers, each with its own consistency and replication model. Process replication replicates processes in a mobile setting, which may require cloning or higher-level mechanisms such as goal-passing (Ch. 3).
M3 ends with a “fast scan of the Web” of replication and consistency for fault tolerance:
| Consistency type | Key mechanism / protocol | Typical systems / tech |
|---|---|---|
| strong | Raft, Paxos | etcd, Spanner, CockroachDB |
| eventual | Gossip, Merkle trees | DynamoDB, Cassandra, Riak |
| causal | Vector clocks, CRDTs | AntidoteDB, Orleans, Akka |
| tunable | Quorums (R/W) | Cassandra, Dynamo-style DBs |
| transactional | Consensus + TrueTime | Spanner, CockroachDB |
| log-based | ISR, CDC streams | Kafka, Debezium, Aurora |
The framing is the point: there is a lot to see before we can understand (almost) all of it, e.g. logical time (Ch. 2) and group and coordination algorithms (Ch. 6). The Kubernetes class (Ch. 9) gives concrete examples.
With N replicas, a write waits for W acknowledgements and a read collects R answers. If R + W > N, every read quorum intersects every write quorum, so a read reaches at least one replica holding the latest completed write (recognised by its version). Tuning R and W trades latency against how many unreachable replicas each operation tolerates.
Replication. Theory and Practice [Charron-Bost et al., 2010] shows how much this basic course leaves out; after it, you should read that book proficiently. Other books: Kemme et al. [2010], Helal et al. [2002], Özsu & Valduriez [2020]; for MySQL, Bradford & Schneider [2012] and Schwartz et al. [2012]; for PostgreSQL, Böszörmenyi & Schönig [2013]; for Veeam, Childerhose [2022].
Lessons learnt · M3
Continuing to provide services in spite of failures is supposed to be a main benefit of distributed over centralised systems [Friedman & Birman, 1996]. The intuition: if a component fails, or is disconnected or partitioned, others replace it and hide the failure, or at least reduce its perceived impact. A system hiding (most of) its failures is highly available (Ch. 4). The design question: how much failure can a system sustain before failure is noticed?
We want systems consistent (correct replies) and available (live, making good things happen), yet they suffer power losses, crashes, network failures, message loss, malicious attacks, Byzantine failures: they are unreliable [Gilbert & Lynch, 2012]. Hence: “The CAP theorem is one example of a more general tradeoff between safety and liveness in unreliable systems.”
Informally, it is only possible to provide any two of consistency (C), availability (A) and partition tolerance (P) [Shim, 2012]. In Zhao's [2014] words: C, replicated data is always consistent; A, data is highly available to users; P, the system keeps providing services when the network partitions. The first formulation is Brewer's:
A distributed database potentially features three desirable properties: Consistency, Availability, and tolerance towards network Partition. According to the CAP theorem, any shared-data distributed system can have at most two of these three.
An impossibility result: “we repent and renounce”. What is our sin? Distributed systems, that's what it is. So pick one to give up:
But the three properties are not of the same sort, technically or conceptually:
Location-based services use a user's or device's position to provide information, entertainment, security [Shekhar et al., 2016]; location-based games use it to evolve the gameplay (BotFighters, GeoZombie [Prandi et al., 2016], Ingress, Pokémon Go, Harry Potter: Wizards Unite, Minecraft Earth). Their CAP profile:
Note the mix: cached replicas for performance (1, 3), strong consistency only where a wrong answer is unacceptable (4), agreement by determinism instead of synchronisation (6).
A proof needs a precise formulation. Gilbert & Lynch [2002] soon gave one, with some limitations; others followed. First, the concepts.
“For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response.” If the system is available, we get responses.
A consistent service is modelled as an atomic data object: operations are totally ordered, and each operation occurs in a single instant of time. Among the consequences, all read operations occurring after a write operation completes must return the value of that write or of a later one. If the system is consistent, we get correct responses.
This C is unlike ACID's: it encompasses both the A (atomicity) and the C (consistency) of ACID.
“When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost.” “And, any pattern of message loss can be modelled as a temporary partition separating the communicating nodes at the exact instant the message is lost.”
Roughly: A sends a message to B. The network is partitioned if it does not reach B; availability is B responding; consistency is B's response being correct.
Atomic consistency is today called linearisability [Herlihy & Wing, 1990]: sequential consistency (§3) whose single order also respects the real-time order of non-overlapping operations. So linearisable ⇒ sequential ⇒ causal. A read returning an old value after a write has completed is allowed by sequential consistency and forbidden by atomic consistency; CAP is about the latter.
The proof is given for three sorts of network:
The slides focus on the asynchronous model: no single clock; nodes act on local computation and received messages.
“It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: availability; atomic consistency — in all fair executions (including those in which messages are lost).”
Assume, for contradiction, that atomicity, availability and partition tolerance all hold. Split the nodes into disjoint, non-empty sets G1, G2, with all messages between them lost. The atomic object o starts at v0.
Run α1 then α2. Nothing from G1 reached G2, so G2 cannot tell this run from α2 alone, where the answer must be v0. It returns v0 although v1's write has completed: atomic consistency is violated. Q.E.D. Instrument 3 replays it and shows the two ways out: answer and be stale (AP), or refuse and stay correct (CP).
Two replicas of one object, initially v0. Choose a policy, cut the link, then write at G1 and read at G2. Replay the proof runs α1 then α2 for you.
Without message loss the asynchronous result still holds: a node cannot tell an arbitrarily delayed message from a lost one. With partial synchrony, local clocks allow timeouts, yet the impossibility remains once messages can be lost; only a weaker, time-bounded consistency becomes achievable [Gilbert & Lynch, 2002].
Should we stop distributing systems, as we stopped using axiomatic systems after Gödel [1931]? Of course we did not. Negative results set the boundaries, and an impossibility result becomes a lever for effective engineering. Brewer later gave a very simple scheme [Brewer, 2012]:
So CAP does not say you always lose a property; it says what to decide while the network is split (in Instrument 3, with the link up both policies answer correctly).
ACID semantics (Atomicity, Consistency, Isolation, Durability) might be too strong [Fox et al., 1997]: “The design space for network services can be partitioned according to the data semantics that each service demands.” For many services “the primary value to the user is not necessarily strong consistency or durability, but rather high availability of data”. What such services can accept instead:
BASE: Basically Available, Soft state, Eventual consistency.
Most cloud services nowadays adopt BASE, e.g. eBay and Amazon DynamoDB, and try to mask inconsistencies from users [Birman et al., 2012]. The slides note that Amazon S3 allows strong read-after-write consistency, and that DynamoDB writes are eventually consistent, reads too, but strongly consistent reads can be configured (at a higher cost). Steps ahead lead to new data-consistency models.
Brewer [2012] sums up: “The modern CAP goal should be to maximise combinations of consistency and availability that make sense for the specific application. Such an approach incorporates plans for operation during a partition and for recovery afterward, thus helping designers think about CAP beyond its historically perceived limitations.” In Instrument 3, healing an AP partition reconciles concurrent writes by last-writer-wins.
Lessons learnt · C1
The exam is a discussion of your project, so expect “why” questions rather than recitation. Practise answering these out loud in two minutes each.
Copies drift once one is modified. Tight consistency needs every update applied atomically everywhere: global synchronisation, costing time, bandwidth and computation, and unavailable during partitions. When and how updates propagate is the real cost, plus machines and personnel.
W(x)1; R(y)0 ∥ W(y)1; R(x)0 causally but not sequentially consistent?Both reads returning 0 needs each read before the other's write: with program order, a cycle, so no interleaving. The writes are concurrent, so causally each process may see its own first.
Vanishing e-mail (monotonic reads), library versions out of order (monotonic writes), new password rejected (read your writes), comment without its post (writes follow reads). Each breaks when the new replica lacks an update the client already saw or made.
In an asynchronous network, no read/write object guarantees both availability and atomic consistency in all fair executions, including those with message loss. Sketch α1 / α2 and indistinguishability.
P is not a choice: networks partition, especially in IoT. C and A are spectra. Without a partition you get both [Brewer, 2012]. The question is what to do during a partition and how to recover.
nodedown and the thief asks another.| Slides | Content | Here |
|---|---|---|
| M3 · Prologue | Disclaimer | §1 |
| M3 · Why replication? I–IV | Reasons; benefits | §1 |
| M3 · Issues I–IV | Costs; consistency; Web caching | §1 |
| M3 · Scaling technique I–VI | N ≪ M; tight consistency; dilemma; relaxing | §1 |
| M3 · Consistency | Models; data first; data store; contract | §2 |
| M3 · Data-centric | Continuous; conit; ordering; sequential; causal | §3 |
| M3 · Client-centric | Switching perspective; eventual consistency | §4, §3 |
| M3 · Client-centric | The four guarantees | §4 |
| M3 · Replication | Replica, service, process replication | §5 |
| M3 · More on replication I–II | Books | §5 |
| M3 · Fault tolerance? I–II | Technology table | §5 |
| M3 · Conclusion | Lessons learnt | §5 |
| C1 · Availability, consistency, failure | Hiding failure; safety vs liveness | §6 |
| C1 · CAP at a glance | Statements; pick one I–II | §6 |
| C1 · CAP at a glance | Location-based games I–III | §6 |
| C1 · Pokémon Go | Google Cloud I–III | §6 |
| C1 · Some proof | One way to see CAP (diagram); conjecture to theorem; C, A, P | §7 |
| C1 · Some proof | Theorem I–II; proof I–II | §7 |
| C1 · Building on CAP | Impossibility; switching strategy | §8 |
| C1 · Building on CAP | ACID vs BASE; beyond BASE; CAP today | §8 |
| C1 · Conclusion | Lessons learnt | §8 |