In a program running on a single machine, the question "what happened first?" always has an answer: you just look at the clock or at the order of the instructions. In a distributed system, that question becomes surprisingly hard. Each node has its own clock, those clocks never agree exactly, and messages take a variable amount of time to arrive. When Anna, in Barcelona, and Mark, in Valencia, press "buy" on the last unit of aged cheese from Montblanc Dairy, deciding who was first is not a matter of looking at two timestamps.

This lesson explains why there is no global clock and how far physical clocks can be synchronised (NTP, PTP). Above all, it presents the solution Leslie Lamport proposed in 1978, which is still fundamental today: replacing physical time with a logical order based on causality. We will implement Lamport clocks and vector clocks step by step in Python, see how they detect concurrent events, and finish with an overview of hybrid clocks and TrueTime, which combine the best of both worlds.

1. Why there is no global clock
2. Physical clocks: drift and synchronisation (NTP and PTP)
3. The problem of ordering events: Anna, Mark and the last cheese
4. The "happens-before" relation
5. Lamport logical clocks
6. Vector clocks
7. Hybrid clocks and TrueTime: an overview
8. Logical clocks in practice
9. Common mistakes and tips
10. Exercises
11. Conclusion

A "global clock" would be a shared, exact instant in time that every node could consult. It does not exist, for three reasons that compound one another:

1. Each node has its own hardware clock, a quartz oscillator whose frequency depends on temperature, age and manufacturing. Two identical clocks, set at the same moment, inevitably drift apart.
2. Reading another node's clock takes time, and that time is variable and unknown. If you ask "what time is it?" and the answer takes 30 ms to arrive, is the time you were given from 15 ms ago? From 5? From 25? You do not know.
3. Nodes pause without knowing it. A process can stop for tens or hundreds of milliseconds because of a garbage collection, a virtual machine interruption or CPU overload. When it resumes, it believes that "now" is the instant at which it stopped.

The practical consequence: two timestamps taken on different machines cannot be compared with a precision better than the synchronisation error between them. If that error is 10 ms and the timestamps differ by 2 ms, the real order is undetermined.

Drift is the rate at which a clock deviates from real time. A typical server quartz crystal has a drift of about 50 parts per million (ppm): it deviates by 50 microseconds every second, that is, about 4.3 seconds a day. It does not sound like much, but for a system processing hundreds of orders per second, 4 seconds is an eternity. That is why clocks are periodically synchronised with a reference source.

NTP is the protocol almost every operating system uses to set its clock over the Internet. It works as a hierarchy of "strata": stratum 0 servers are atomic clocks or GPS receivers; stratum 1 servers synchronise directly with them; stratum 2 servers with stratum 1, and so on. An NTP client sends a request, notes when it sent it and when it received the response, and uses the server's timestamps to estimate the offset, assuming that the outbound trip takes as long as the return trip. That assumption is the main source of error.

Furthermore, NTP adjusts the clock in two ways: by slewing, slightly speeding up or slowing down the clock until the offset is corrected, or by stepping, if the offset is large. A step backwards means that the clock may show the same instant twice, or that a duration measurement (end - start) may come out negative. For this reason operating systems offer a monotonic clock (time.monotonic() in Python), which never goes backwards and is used for measuring durations, as opposed to the wall clock (time.time()), which tells you the date and time but can jump.

PTP (IEEE 1588) achieves accuracies of microseconds or better because the timestamps are applied in hardware by the network cards and switches themselves, removing the variability of software. It requires compatible hardware along the whole path, so it is used in data centres, high-frequency finance and telecommunications, not on the open Internet.

Even with PTP, clocks have an error. And that error, however small, is enough for two "almost simultaneous" events to be impossible to order with certainty. We need a different idea.

Suppose Kilometre Zero has replicated the inventory service in two cities to reduce latency: one replica in Barcelona (inv-bcn) and another in Valencia (inv-vlc). There is one unit of aged cheese from Montblanc Dairy left. Anna buys from Barcelona and Mark from Valencia, almost at the same time.

If we trust the clocks, Mark was 2 ms earlier. But the clock on inv-vlc is synchronised via NTP with an estimated error of ±15 ms. So Mark's "true" time lies between 10:00:00.103 and 10:00:00.133: it may have been before or after Anna. Physical clocks cannot decide.

And now the key question: does "who was first" in physical time really matter? What the system needs is for both replicas to make the same decision (one of the two purchases wins, the other gets "out of stock") and for that decision to respect the cause-and-effect relationships we do know about. For example, if Anna checked the stock, saw "1 unit" and then bought, her purchase happened after her check, and that much is a fact.

This is Lamport's idea: give up on physical time and keep only what we can know for certain, causality.

Lamport defined the happens-before relation (written a → b, "a happened before b") from just three rules:

1. Same process. If a and b are events in the same process and a occurs before b in its execution, then a → b.
2. Send and receive. If a is the sending of a message and b is the receipt of that same message, then a → b.
3. Transitivity. If a → b and b → c, then a → c.

And one fundamental definition: if neither a → b nor b → a, then a and b are concurrent (a ∥ b). Concurrent does not mean "at the same time": it means that neither could have influenced the other, because there is no chain of messages connecting them. That is why, as far as the system is concerned, their order is irrelevant: any order is equally valid, as long as all nodes choose the same one.

In this diagram: a2 → a3 (same process), a3 → a4 → m4 (send and receive, plus transitivity). But a3 and m3 (the two purchases) are concurrent: there is no chain of messages between them. The system cannot know which was "really" first, and it does not need to: what it needs is a deterministic rule to break the tie.

A Lamport logical clock is one integer counter per process that assigns each event a stamp L(e) such that the clock condition holds: if a → b, then L(a) < L(b). The algorithm has three rules, mirroring the three happens-before rules:

1. Before each local event, the process increments its counter: L = L + 1.
2. When sending a message, the process increments its counter and attaches the value to the message.
3. When receiving a message with stamp Lm, the process sets L = max(L, Lm) + 1.

Rule 3 is the key: it guarantees that the receipt always has a higher stamp than the send, and that from that moment on the receiver "knows" that at least that logical time exists.

The output:

The same scenario, drawn as a sequence diagram with the Lamport stamp of each event:

Important observations:

1. The clock condition holds. Every receipt has a higher stamp than its send (1 → 2, 2 → 3, 5 → 6), and within each process the stamps increase. Every causal chain has increasing stamps.
2. There are ties. "Anna buys" (inv-bcn, 4) and "Mark checks" (inv-vlc, 4) have the same stamp. Lamport resolves ties with an arbitrary but deterministic criterion: if the stamps are equal, order by the name (or identifier) of the process. That is what sorted(...) does with the (stamp, name, description) tuples. This way, every node that applies the same rule will obtain the same total order.
3. The total order is not "the real order", and it does not matter. In the final order, "Anna buys" (4) comes before "Mark buys" (5). Was that the case in physical time? We do not know, and we cannot know. But it is an order consistent with all the known causality and it is the same for everyone, which is exactly what we needed to decide who gets the cheese.
4. The limitation of Lamport clocks. If a → b, then L(a) < L(b). But the converse is false: L(a) < L(b) does not imply a → b. "Anna buys" (4) has a lower stamp than "Mark buys" (5), yet they are concurrent events: there is no causal relationship between them. By looking at Lamport stamps alone we cannot tell "happened before" from "concurrent". For that we need vector clocks.

A vector clock replaces the single integer with a vector holding one counter per process. If there are three processes, each event carries a stamp such as {inv-bcn: 3, inv-vlc: 1, dairy: 2}, which reads as "this event knows about everything up to Barcelona's event 3, Valencia's event 1 and the dairy's event 2". The rules:

1. Before each local event, process i increments its own component: V[i] = V[i] + 1.
2. When sending, it increments its component and attaches the whole vector to the message.
3. When receiving a message with vector Vm, it sets V[k] = max(V[k], Vm[k]) for every component k, and then increments its own component.

And the comparison, which is what we gain:

• V(a) ≤ V(b) if all the components of V(a) are less than or equal to those of V(b).
• a → b if and only if V(a) ≤ V(b) and V(a) ≠ V(b).
• a ∥ b (concurrent) if neither V(a) ≤ V(b) nor V(b) ≤ V(a): that is, each has some component greater than the other's.

Now the converse does hold: by comparing vectors we can know for certain whether two events are causally related or concurrent.

The output:

Let's look at what we have gained:

1. We detect concurrency. a3 (Anna buys) has inv-bcn:3, greater than in m3, but m3 (Mark buys) has inv-vlc:3, greater than in a3. Each one "knows something" the other does not: they are concurrent, and the system can detect it mechanically. With Lamport clocks, this was impossible.
2. We confirm causality. a3 → m4: when Valencia receives the notice from Barcelona, its vector absorbs Barcelona's (inv-bcn:4), and from then on everything that happens in Valencia "knows" about Anna's purchase. The vector of m4 dominates that of a3 in every component.
3. A subtle detail: d1 → m3. The dairy sent d1 to Barcelona, not to Valencia, so how come m3 "knows" about d1? Because d2 happened after d1 at the dairy (same component: 2 > 1), and m1 received d2. Transitivity propagates by itself through the vector.
4. The price. Each stamp takes up as many integers as there are processes. With 3 processes that is trivial; with 1,000 replicas or millions of clients, it is not. In practice, systems use vectors containing only the nodes that write (not the clients), or compacted variants (dotted version vectors), or they accept Lamport's loss of information when there is no need to detect concurrency.

Logical clocks solve causal ordering, but they lose something valuable: the link with real time. A Lamport stamp of 4732 says nothing about whether the event happened this morning or last year, and many uses (auditing, expiry, "give me the orders from the last hour") need physical time. Two families of solutions combine both worlds:

• Hybrid logical clocks (HLC, 2014). An HLC stamp has two parts: the physical time (according to NTP) and a logical counter. It behaves like a Lamport clock (it respects causality: if a → b, then HLC(a) < HLC(b)), but its physical part always stays close to real time (with an error bounded by NTP's). The logical counter only comes into play to break ties between events that physical time cannot order. They are used by distributed databases such as CockroachDB and MongoDB.
• TrueTime (Google Spanner, 2012). Instead of giving one instant, the TrueTime API returns an interval [earliest, latest] that is guaranteed to contain the real instant, thanks to atomic clocks and GPS in every data centre, which keep the interval down to a few milliseconds. Spanner assigns each transaction a timestamp and, before committing it, waits until the uncertainty interval has completely passed (commit wait). This guarantees that if transaction A finished before transaction B started in real time, then A's timestamp is lower than B's, anywhere in the world. It is an expensive solution (specialised hardware) but a conceptually elegant one: it turns clock uncertainty into an explicit, bounded wait.

Where do these mechanisms show up in real systems, and at Kilometre Zero?

• Ordering messages and events. When the delivery service receives positions from couriers over 4G, they may arrive out of order. If each position carries a per-courier counter (a single-process Lamport clock), delivery can discard old positions that arrive late. Messaging systems (lesson 02-04) offer ordering guarantees based on the same idea of sequence numbers.
• Conflict detection in replication. When two replicas of inventory (or two copies of Anna's basket, one on her phone and one on the server) are modified concurrently, version vectors make it possible to tell a genuine conflict (two concurrent writes) from a simple update (one write that happened after the other). The system can then resolve the conflict (with a business rule, by asking the user, or by keeping both versions). This is the mechanism popularised by Amazon Dynamo, which we will study in lesson 03-04.
• Consistent snapshots. For analytics to calculate "the total stock at 12:00" over data spread across many replicas without stopping the system, it needs to know which events to include. Logical clocks make it possible to define consistent cuts (the Chandy-Lamport algorithm) that never include an effect without its cause.
• Transaction timestamps. Distributed databases assign timestamps (HLC, TrueTime) to transactions to decide which version of a piece of data each read sees. This will come up in Module 3 and in lesson 04-04.

The practical rule that follows from all this: never use physical timestamps taken on different machines to decide the order of operations that affect data consistency. Use them for what they are good for (dates for humans, expiry, metrics) and use counters or vectors for ordering.

• Using time.time() to measure durations. The wall clock can jump backwards because of an NTP adjustment and give negative or absurd durations. To measure how long something takes, always use time.monotonic().
• Ordering events from different nodes by their physical timestamp. This is the clock-based last-writer-wins mistake: with out-of-sync clocks, an older write can "beat" a more recent one and silently lose data. If you use that strategy, you need to be aware that it can lose writes.
• Believing that Lamport clocks detect concurrency. L(a) < L(b) tells you nothing about the causal relationship between a and b. If you need to know whether two events are concurrent, you need vectors.
• Forgetting the deterministic tie-break. A Lamport total order requires a rule for ties (usually the process identifier). Without it, two nodes may order two events with the same stamp differently.
• Vectors that grow out of control. If every client that writes adds a component to the vector, the vector grows without bound. You have to decide who "counts" as a process (normally the replicas, not the clients) and prune old components.
• Tip: in every message or record that crosses the network, always include two things: a physical timestamp (for humans and for metrics) and a sequence number or vector (for ordering). They cost a few bytes and save hours of debugging.

Three processes, orders, payments and analytics, start with their clocks at 0. The following events occur, in this order of execution:

1. orders local event "creates Lucy's order".
2. orders sends "charge €14.50" to payments.
3. analytics local event "starts report".
4. payments receives the message from orders.
5. payments local event "charge accepted".
6. payments sends "charge OK" to orders and also to analytics (two consecutive sends).
7. analytics receives "charge OK".
8. orders receives "charge OK".

Work out the Lamport stamp of each event and name two events that are concurrent even though their stamps are different.

Anna modifies her basket from her phone (process mobile) and from the browser (process web), and both sync with the server (process server). Using the VectorProcess class, simulate:

1. server sends the initial basket to mobile and to web (two sends).
2. mobile receives it, and adds "fresh cheese" (local event).
3. web receives it, and adds "red wine" (local event).
4. mobile sends its basket to the server; the server receives it.
5. web sends its basket to the server; the server receives it.

Use concurrent() to check whether the two modifications are concurrent and explain what the server should do. Then change the order so that web receives the basket from the server after the server has merged in the one from mobile, and check that the web modification now happens after the mobile one.

The delivery service receives positions from a courier over a network that reorders them. Write a CourierTracker class with a receive_position(sequence, lat, lon) method that only updates the current position if sequence is greater than the last one applied, and that counts how many positions it has discarded as stale. Simulate the arrival of the sequences [1, 2, 4, 3, 5, 7, 6, 8] and show the final position and the number of discards. What information is lost with this strategy, and when would that be acceptable?

Solution 1:

Concurrent events with different stamps: "starts report" (analytics, 1) and "charge accepted" (payments, 4). There is no chain of messages between them (analytics had not received anything yet), so they are concurrent, even though 1 < 4. Another pair: "creates order" (1) and "starts report" (1), with equal stamps and also concurrent. Notice that "starts report" (1) and "receives charge OK" on orders (6) are concurrent as well: the 6 on orders descends from payments, not from analytics.

Solution 2:

The result is {server:1, mobile:2, web:0} versus {server:2, mobile:0, web:2}: concurrent. Neither modification knew about the other. The server must not simply keep whichever arrived last (it would lose the cheese or the wine): it must merge the two (a basket with cheese and wine) or, if the merge is not obvious (for example, both changed the quantity of the same product), ask Anna.

In the sequential variant (the server first merges in the basket from mobile and then sends the updated basket to web, which then adds the wine), the stamp of w2 will be something like {server:3, mobile:3, web:2}, which dominates mb2: mb2.happened_before(w2) is True. There is no conflict: the web modification already knew about the mobile one, and the server can simply apply it.

Solution 3:

The final position is the one from sequence 8, and 2 positions are discarded (3 and 6). What is lost is the complete route: if analytics wanted to reconstruct the exact route, two points would be missing. The strategy is acceptable when only the current position matters (showing the courier on the map), which is the case for real-time tracking; if the history is needed, all positions would have to be stored and sorted by sequence afterwards, instead of being discarded.

There is no global clock: each node has its own, with its own drift, and synchronising them (NTP with millisecond accuracy, PTP with microsecond accuracy) reduces the error but never eliminates it. That is why the order of two events that occurred on different machines cannot be decided by comparing their physical timestamps, as the case of Anna and Mark buying the last cheese shows.

Lamport's way out was to change the question: instead of "what occurred earlier in time?", ask "what could have caused what?". The happens-before relation captures exactly that causality, Lamport clocks turn it into a total order that all nodes share (at the cost of not distinguishing concurrency), and vector clocks add the ability to detect when two events are concurrent, which is the basis of conflict detection in replication. Hybrid clocks and TrueTime reconcile causality with real time for the systems that need both.

This brings the conceptual foundations of the module to a close. The next lesson, From Monolith to Distributed Platform: the Kilometre Zero Case, gathers everything we have seen (partial failures, models, advantages and costs, fallacies, time) and applies it to a concrete design: the target architecture we will build over the rest of the course.