Distributed systems: latency, partitions, consistency

The starting question

You send a 5 MB file to a distant server. Your connection advertises 40 Mbit/s. How long will it take? Many answer: "5 MB = 40 megabits, so one second". That is wrong as soon as the server is far away. The latency is missing.

Two different quantities

• Bandwidth: how many bits pass per second, in Mbit/s. It is the width of the pipe.
• Latency: the time for a message to go from one point to another. Often we speak of the round-trip time (RTT). It is the length of the pipe.

A truck can carry an enormous amount of data (high bandwidth) but take a day (high latency). An SMS is small but arrives quickly.

A physical limit

Light in an optical fibre travels at about 200,000 km/s, roughly two thirds of its speed in vacuum. This is not an operator's flaw: this limit holds for conventional fibre; only the speed of light in vacuum is an absolute bound (microwave or hollow-core links get closer to it, without exceeding it). Take two hypothetical data centres 6,000 km apart:

• one way: at least 6,000 ÷ 200,000 = 0.03 s = 30 ms;
• round trip: at least 60 ms, in reality more, because fibre does not follow the straight line and routers add delays.

A worked example: the workshop's simplified model

Total time = (number of setup round trips) × RTT + size × 8 ÷ bandwidth. For 5 MB, 40 Mbit/s, RTT = 120 ms and 2 setup round trips:

• transmission: 5 × 8 ÷ 40 = 1 s = 1,000 ms;
• setup: 2 × 120 = 240 ms;
• total: 1,240 ms.

Divide the size by 10 (500 KB): transmission falls to 100 ms but setup stays at 240 ms. For small messages latency dominates; for big files, bandwidth. A consensus message is small: the whole life of a consensus protocol is therefore paced by round trips.

Explore the request-path tool: DNS, TCP, TLS then HTTP chain several exchanges before the first useful byte flows. The model is deliberately simplified (for example it ignores reused connections).

The key point: slow or dead?

Node A sends a request to B and waits. After 2 seconds without an answer, what does A know? Nothing certain. B may have crashed, the network may have lost the message, or the reply may arrive in 3 seconds. From A's side these three cases are indistinguishable. The only weapon is the timeout, which is an assumption, not a proof: set too short, it declares a merely slow node "dead"; too long, it delays every reaction.

What this does NOT guarantee

A low RTT measured this morning does not guarantee tomorrow's. Latency varies (congestion, changed route); a serious protocol assumes no bound, or states one explicitly as an assumption.

Recap

• Bandwidth = width of the pipe, latency = its length; small messages are dominated by latency.
• Light in fibre sets a minimum of roughly 1 ms of round trip per 100 km (an order of magnitude).
• A slow node cannot be told from a dead one; a timeout is a bet.

The starting question

For a ledger to survive a machine failing, we replicate it: three copies, A, B and C, on three sites. One day, the cable between A and the other two is cut. A, B and C all run, but A no longer receives anything from B and C, and vice versa. What should the system do?

The concept: the partition

A network partition is a situation where nodes are split into groups that can no longer exchange messages, while every node is running. It can come from a cut cable, a saturated router, a misconfigured firewall, or an attacker. From A's side, it looks like B and C failing (lesson 1).

A worked example: a replicated balance

An account with balance 100 is replicated on A, B, C. Partition: A is alone on one side; B and C together on the other.

• At 10:00, Aminata withdraws 80 through A.
• At 10:01, Bello, who shares the account, withdraws 80 through B.

Option 1: everyone answers (availability). A accepts (local balance 20), B accepts (local balance 20 on B and C). The network recovers: both withdrawals are in the log, the balance "should" be 100 − 160 = −60. The invariant "no negative balance" is broken; you must reconcile (cancel a withdrawal? overdraft?).

Option 2: only the majority answers (consistency). A quorum rule requires 2 replicas out of 3 to confirm every operation. B and C (2 of 3) have the quorum and accept Bello's withdrawal. A (1 of 3) does not: it refuses to answer Aminata ("try again later"). No negative balance, but Aminata is blocked.

Why quorums work: overlapping

With N replicas, if a write must be confirmed by W replicas and a read queries R replicas, with R + W > N, every read meets at least one up-to-date replica. Here N = 3, W = 2, R = 2: 2 + 2 > 3. Two sets of 2 out of 3 always overlap (in at least one node). Careful: R + W > N only guarantees overlap between a read and a write. To also forbid two concurrent writes on disjoint sets, you additionally need 2W > N (here 2 × 2 > 3, which holds). With N = 5, W = 2 and R = 4, R + W > N holds, yet two writes of 2 replicas each can be disjoint. In our example, two groups each holding a write quorum therefore cannot exist side by side.

What each option sacrifices

No option gives both "everyone is served" and "a single state".

Your turn

Reproduce the table with another scenario: 5 replicas, a 2 | 3 partition. Which half holds the quorum (3 of 5)? How many replicas can fail before the quorum is lost?

What this does NOT guarantee

A read and write quorum with R + W > N guarantees a read sees the latest confirmed write under simple assumptions (no faulty node, correct read protocol). It does not by itself settle concurrent writes, or failures that strike mid-write: that is the job of consensus protocols.

Recap

• A partition cuts the network without stopping the machines; each side believes the other has failed.
• Either answer everywhere (and reconcile later), or demand a majority (and block the minority).
• With R + W > N, every read quorum meets a write quorum; with 2W > N, two write quorums also meet.

The starting question

CAP is often summed up as "pick two out of three: Consistency, Availability, Partition tolerance". The slogan is misleading. What does the theorem actually say?

The precise statement

The three words have a strict meaning:

• Consistency (in CAP's sense): linearizability. The system behaves as if there were a single copy, and every read returns the latest completed write.
• Availability: every request received by a non-failing node gets a response (not an error, not silence).
• Partition: the network may lose or arbitrarily delay messages between nodes.

The theorem (Brewer's conjecture, proved by Gilbert and Lynch in 2002 in an asynchronous network model) says: during a partition, a system cannot be both consistent and available. The two options of lesson 2 are exactly these two branches.

The classic misreadings

1. "Partition" is not a choice. In a real network, partitions happen. You do not choose whether to "tolerate" them: you choose, when they happen, between consistency and availability.
2. Without a partition, you can have both. CAP says nothing about normal operation.
3. It is not binary. Between "linearizable" and "everything diverges" lies a spectrum of guarantees.
4. Even without a partition, there is a cost: guaranteeing consistency requires communicating, hence paying round trips (lesson 1). This latency/consistency trade-off is formalised in later work building on CAP (Abadi names it PACELC).

Two families of guarantees

A worked example: reconciling by "last write wins"

Two replicas each accept a change to the same field during a partition: replica A writes "address = Douala" at local time 10:00:05, replica B writes "address = Yaoundé" at 10:00:03. Rule "last write wins" (LWW): keep 10:00:05, so Douala. But if A's clock ran 4 seconds fast, A's write actually happened at 10:00:01, before B's: the wrong one was kept. The rule depends on clocks that are not reliable (lesson 4). It is simple but loses writes.

Where do blockchains fit?

• Proof-of-work networks such as Bitcoin behave, during a partition, rather like available systems: each side keeps producing blocks, then, on repair, the chain with the greatest cumulative work wins and the other side is abandoned. This is eventual consistency with probabilistic finality. This characterisation is common but simplifying.
• BFT-type protocols with deterministic finality require more than two thirds of the votes: without them, they halt rather than contradict themselves (you will see this in detail in workshop 108).

What this does NOT guarantee

Filing a system under a "CP" or "AP" label is a simplification: the same database may behave differently depending on its configuration, its operations and its failures. The label is for asking the right questions, not for concluding.

Recap

• CAP: during a partition, linearizable consistency and availability of everyone cannot coexist.
• The partition is not an option; what you choose is the reaction.
• Strong consistency = no divergence but possible unavailability; eventual consistency = answers everywhere but reconciliation.

The starting question

Two machines claim: "I received the transaction at 10:00:05" and "I received the other at 10:00:04". Which arrived first? If clocks could be trusted, the answer would be immediate. They cannot.

Why no reliable global clock exists

1. Drift. Each machine has its own quartz oscillator. An ordinary quartz can drift by a few tens of parts per million: 20 ppm gives 20 × 10⁻⁶ × 86,400 s ≈ 1.7 seconds per day. The gap grows until someone corrects it.
2. Synchronisation is imperfect. Protocols such as NTP bring the gap down to a few milliseconds to a few tens of milliseconds over the public Internet, but the gap stays unknown and variable, since it depends on network delays, themselves asymmetric and uncertain (lesson 1).
3. A remote clock cannot be read instantly. Even a perfect clock cannot be read from a distance without delay: the message carrying the time has an unknown, possibly asymmetric delay.

Practical consequence: if two events are closer together than the clocks' uncertainty, their order according to the clocks is meaningless.

Ordering without the time: the "happened-before" relation

A safe order exists all the same, through causality: event a happened before b if (1) a and b are on the same machine and a is earlier, or (2) a is the sending of a message of which b is the receipt, or (3) by transitivity. Two events with no such chain are concurrent.

Lamport logical clocks (Lamport, 1978) give each event a counter:

1. before each local event or send, increment your counter by 1;
2. attach the counter to messages sent;
3. on receipt, set the counter to max(local counter, received counter) + 1.

A worked example

• P1: local event a → 1; send m1 → 2 (m1 carries 2).
• P2: local event → 1; receive m1 → max(1, 2) + 1 = 3; send m2 → 4.
• P3: five local events → 5; receive m2 → max(5, 4) + 1 = 6.

Guaranteed property: if a happened before b, then L(a) < L(b). The converse is false: L(a) < L(b) does not imply a preceded b; they may be concurrent. Two concurrent events can even have the same counter (ties are broken by node id to obtain an arbitrary but consistent total order).

And blockchains?

A block carries a timestamp, but it is not a reliable clock: in Bitcoin, the consensus rule requires a block's time to exceed the median of the previous 11 blocks and not to be more than two hours ahead of the network time as the node computes it (how that time is computed depends on the client). A window of several hours shows the timestamp is a coarse bound, not a stopwatch. What really orders blocks is their chaining (each block cites the previous one) and the chain-selection rule.

What this does NOT guarantee

A logical clock says nothing about the real duration between two events, nor about civil time. For billing, compliance or a legal log, you need timestamps from a trusted source, with their margin of error.

Recap

• Clocks drift and their synchronisation has a margin of error; no reliable global time exists.
• Causality (send before receive) gives a safe partial order; Lamport turns it into a counter.
• L(a) < L(b) does not imply "a before b"; only the converse is guaranteed.